The church has a complex building history, each phase of which has left traces in the fabric. The earliest discernable form is of an aisleless 12thc. nave (see the round-headed window scar in the N arcade wall above bay 2). The N wall was pierced for this four-bay arcade towards the end of the century, and a N aisle added. The arcade has round-headed, unchamfered arches and quatrefoil piers, but the lower parts of two of the piers are of a different form; one cylindrical and the other octagonal. Pevsner considers this to be a later encasing, designed to alter the arcade design but not completed. The alternative is that the more solid pier forms represent an earlier state of the arcade, but on balance Pevsner's explanation seems more likely, especially in view of the octagonal pier forms of the S arcade. This dates from after 1298, when a good deal of work was carried out (see VII History).

The chancel has N and S chapels, extensions of the aisles, and the chancel arch and chapel arches belong to the same campaign as the S arcade, as do many of the Y-traceried windows and the S nave doorway. The slender W tower belongs to a similar or slightly later date in its lower storeys, up to the level of the reticulated bell-openings, but it was heightened in the 15thc. with a new bell-storey above, and a wooden spire (demolished c.1645). The nave has also been heightened, for the addition of a 16thc. clerestorey, but the earlier roofline is clearly seen on the W interior wall. The church was restored from 1884-86, with the loss of medieval wallpaintings.

Construction is of ironstone rubble except for the Perpendicular addition to the tower, which is of grey ashlar. In 1999 a Parish Church Centre was added. This was sensitively conceived as a separate building to the W of the church. The N arcade is described below.

According to the Domesday Survey, land in Moulton (1½ hides and 1 bovate) belonged to the royal manor of Kingsthorpe in 1086. A further holding (two hides and 1½ virgates) was in the hands of William, who held it of Robert de Bucy, and three hides and one virgate were held by Grimbald of Countess Judith. In none of these holdings was a church recorded, but Grimbald gave Moulton church to St Andrew's Northampton before 1107. The church was ruined in 1265, during the Barons' War, and rebuilding began in earnest after 1298, following a directive from Bishop Oliver Sutton. This included the aisles, dedicated to St Paul, from which the double dedication arises.