An aisleless cruciform church with rendered nave, crenellated flint crossing tower, south transept and square chancel. Construction appears to be of flint throughout. A plan on show inside the church (1991) indicates that the chancel was originally shorter and apsidal, and that there were two transepts with apsidal chapels. No authority for this plan is given. In 1991 the interior of the nave was inacessible owing to restoration work. By 1998 this had been completed and proved to consist in the main of laying a new floor and altering the liturgical arrangements by installing an altar at the W end of the nave with rows of chairs facing it. According to the churchwarden, the work was overseen by Martin Biddle. The old pulpit remains in its original position, at the E end of the nave and is thus not usable in the new arrangement. The original altar remains in place too, so is presumably used for some services. Romanesque features described below are the S nave doorway, corbels on the S transept, a window in the chancel N wall, and the crossing arches with their capitals.

Cholsey was named in the 1125 foundation charter of Reading Abbey as one of three abbeys which had been destroyed on account of their sins, and their possessions given to Reading by Henry I to finance the new foundation. In Cholsey's case this meant retrieving the church from the Abbey of Mont-Saint-Michel, which held it from the king, along with two priests, at the time of the Domesday Survey. Mont-Saint-Michel received lands in Budleigh, Devon, in exchange, and at the same time alienated demesne land in Cholsey was retrieved from various tenants.

The church is a major one with its crossing tower and transepts with chapels, and there is evidence in the form of long and short work on the tower that some of the fabric belongs to the 11thc. The juxtaposition of the plain, heavy crossing arches and the two elaborate capitals of the W arch is rather odd, and it is possible that the capitals were inserted towards the end of the 12thc.