On 23 December 1849 the first Anglican Church service was held in St Kilda at the home of Henry Jennings in Fitzroy Street. Sometime later a timber building was erected on the present site in Acland Street and licensed for use as a church by Bishop Perry 7 November 1851.
The present church was designed by the architects Albert Purchas (1825-1909) and Charles R Swyer. The foundation stone was laid on 29 November 1854 and the first service in the new building was held on 2 August 1857.