There has likely been a church on this site since the 7th century, but there is no documentary evidence of any building before the present one. The first building is likely to have been of wood and is said to have been founded by St Paulinus (d. 644).All Saints Parish Church It was replaced by a stone building in the 9th century: fragments of this Saxon church have been unearthed at intervals since and are displayed inside.
The outside of the church presents a fairly uniform 15th century appearance in the “Perpendicular” style with its Norman origins clear from the north aisle arcade (c.1120). The south aisle arcade was constructed around 70 years later; but already its pillars are taller and more slender and the arches have pointed tops. The transepts were added in the “Early English” style in the 13th century and a tower was built between them at the crossing. This collapsed in 1318, when Northallerton was sacked by the Scots, and was replaced by the present tower in 1420. Both aisles were also renewed and enlarged in the 15th century, but fortunately the 12th century arcades were retained. The chancel was completely rebuilt in 1885 in an imitation of the “Perpendicular” style by C. Hodgson Fowler.
The interior of the church was extensively refurbished in the late 19th century, when the chancel was rebuilt, and most of the furnishings and stained glass date from then. One exception is the font, which bears the date 1662 and is topped by an 18th century wooden canopy.