The existence of a reset 12thc. doorway confirms that there was a stone church of that date, but there appears to have been a complete rebuilding in the 13thc. The nave with its four-bay aisles belongs to that period, as does the chancel with its broad arch. The E end of the S aisle was widened to form a chapel c. 1330, and in the 15thc. the clerestorey was added. The W tower dates from c. 1500. The main doorway now is in the S aisle, facing the village, and is 13thc. work of some pretension to grandeur. The 12thc. doorway now serving as a priest's door is much too imposing to have fulfilled that function originally, and although it is small for a nave doorway this is what it must have been. The chancel and chancel arch were largely rebuilt in 1880, and the rest of the church was restored from 1888-93, when the south chapel and the east wall of the north aisle were largely rebuilt. In 1901, the upper part of the clerestorey was rebuilt and re-roofed, the aisles repaired and re-roofed, and the south door reset. The north-west corner of the north aisle was partly rebuilt in 1906.The chancel is of ashlar except for the N wall, rebuilt in pebble and reddish ashlar above; the nave clerestorey is of ashlar and the aisles of stone and pebble rubble; the three lower storeys of the tower are of ashlar, and the 4th of stone rubble. The church contains a store of fragments in the nave, including 15th-16thc. window heads, two reliefs with snaking tendrils, a late-medieval base and a section of keeled shaft, but nothing of obviously Romanesque manufacture.

Stow Longa does not appear in the Domesday Survey. The earliest mention of the parish is in the Inquisitio Eliensis (1072-93).

The tympanum apparently did not originally belong with the outer order of nook shafts and arch in which it is housed, but was presumably an 11thc. piece reset in the 2nd quarter of the 12thc. Some account must, however, be taken of the capitals at Castor (Northants - the entire church evidently dated by inscription to 1124), which include both the foliage and angle mask type and examples of animals in low relief. The tympanum at Stow is more obviously related to the Little Paxton tympanum and possibly to the worn relief at nearby Tilbrook. The composition, with three simple beasts carved in low relief, is not readily interpreted by the modern viewer. The temptation is to read it as a series of pictograms rather than any kind of narrative. Adopting this approach, the central siren, who lures sailors onto the rocks with her sweet singing, is generally identified (following the Physiologus and subsequent Bestiary texts) as a warning against deception by the allurements of the world. This caution against temptation must be the chief message of the tympanum, but further analysis is hampered by the problem of identifying the flanking beasts. One possibility is that the creature on the left, with its rough skin and gaping mouth, is a crocodile, representative (in the hydrus story) of hell, and that on the right is a lion, often equated with Christ. The ensemble would then depict man's choice between salvation and damnation when faced with earthly temptation. Keyser (1904) suggests that the animal on the L has its foot on an altar, and that the creature on the R may be the Agnus Dei, probably because of the characteristic folding of one foreleg.