Dating from the era of Marvellous Melbourne, St Paul's stands at the city's southern approach, where from March 1836 the first religious services were conducted under a great gum by Dr Alexander Thomson, 'catechist' of the Port Phillip Association. Originally proposed as the site for the courthouse and gaol, the site was used as a depot for firewood and fodder until, in April 1848, on the application of Bishop Charles Perry, the land was granted for the building of Melbourne's third Anglican church. Building began in September 1850, but because of the shortage of skilled tradesmen following the discovery of gold it was not opened until December 1852. Designed by James and Charles Webb, St Paul's was a substantial bluestone structure occupying the Flinders Street frontage.
Bishop James Moorhouse, Perry's successor, arrived in January 1877 and quickly won approval to build a cathedral, designed by leading English ecclesiastical architect William Butterfield, on the St Paul's site. The style chosen was Transitional Gothic and the governor laid the foundation stone on 13 April 1880. Dissension between the architect and the Cathedral Erection Board led to Butterfield's resignation in 1884, leaving Joseph Reed to oversee the completion of the cathedral according to Butterfield's plans. St Paul's most distinctive feature is its horizontally banded stone interior, but its organ by T.C. Lewis, windows by Clayton & Bell, Venetian glass mosaics and blackwood furniture designed by Reed are also notable.
The cathedral opened in 1891 without its octagonal central tower and twin saddleback western towers. Work began on the more conventional tower and spires designed by John Barr of Sydney in 1926, and they were completed in 1933.