St Paul's stands at the very heart of the County Town of Bedford and serves both as a Parish Church and as the Civic and County Church of Bedfordshire.

Originally constructed in the early 13th century, the present church building has undergone numerous alterations, extensions, rebuilds and restorations since this time. An Early English south porch does survive from the original 13th century structure however, and records trace the existence of a previous Collegiate church on this site as far back as 1066. The Trinity Chapel of the church was first constructed in 1416, with maintenance of the chapel entrusted to the Holy Brotherhood of the Trinity. The church has long standing connections with Sir William Harpur and Dame Alice Harper, and the Trinity Chapel holds brasses of the couple. Sir William was the Lord Mayor of the City of London in 1562, and his Harpur Trust (which has a long history of operating independent schools in Bedford) has donated many of the stained glass windows in the church. Other improvements in the 15th century included Misericords in the chancel and two additional porches. The Trinity Chapel was used as an Archdeacon's Court after the English Reformation.[1]

On May 23, 1656, John Bunyan, the Christian preacher and author of "The Pilgrim's Progress", preached at St. Paul's. John Wesley, the Anglican cleric and Christian theologian (also one of the founders of Methodism) preached the Assize Sermon at the church on 10 March 1758. During the 19th century St Paul's became an Anglo-Catholic church of the Church of England, where it remains. As a result, the Sisters of Saint Etheldreda began to be associated with the parish from 1869. Architectural work to the church in the 19th century includes the tower and spire, transepts, choir stalls, chancel and chancel roof.[1]

Early 20th century work to the church includes the Rood screen (designed by George Frederick Bodley), the English Altar and altar rails (designed by the Bromsgrove Guild), and restoration work to the Trinity Chapel (instituted by C. E. Mallows). Many live broadcasts took place from the church between 1941 and the end of World War II. On one event, a joint mass was celebrated by the Archbishops of Canterbury and York, but throughout the period Daily Services were broadcast regularly from the church by the BBC. The church was also home to a service officiated by Roman Catholic Cardinal Arthur Hinsley. Later in the 20th century, from the mid-1970s to 1982, the church was restored and otherwise improved.