St Paul’s Church was consecrated on 1 November 1865, All Saints Day, by Alexander Penrose Forbes, Bishop of Brechin.

In 1852, when Bishop Forbes and the architect George Gilbert Scott surveyed possible sites for a new church, they chose Castlehill, because of its unique and striking location. St Paul’s Church was intended to be an inspiring addition to Dundee’s skyline, rising above the crowded town centre. The foundation stone (in the Sacristy) was laid on 21 July 1853, and St Paul’s was opened for worship on 13 December 1855. The church cost over £14,000 and it took ten years to clear a considerable debt, hence the delay in consecration. All Saints Day 1865 is recorded in the Latin inscription at the back of the sedilia (the marble bench to the right of the high altar), – in Festo Omnium Sanctorum. Also listed are the Vestry members, the leading figures in fundraising, headed by Sir John Ogilvie, Dundee’s Liberal MP from 1857-1874

Bishop Forbes died on 8 October 1875, aged 59, and is buried under the brass plate in the chancel. His grave was said to be ‘hewn out of the solid rock of the old Castlehill, on which the foundations of the Church rest’. St Paul’s Church was elevated to the status of Cathedral of Brechin Diocese in 1905.