The church is located on the corner of Burwood Road and St Columbs Street.

[1][2] The church is named after St Columb's Cathedral in Derry, Northern Ireland, in honour of Saint Columba (521–597), an Irish abbot and missionary who spread Christianity to Scotland.

[2] The main building was designed by George Wharton in the Decorated Gothic architectural style in 1882-1883.

[3] The stained glass was designed by William Montgomery, Alan Sumner and others.

[3] The current pipe organ, built by Roberts Ltd of Melbourne and Adelaide, has been in this church since 1923.