The prominent Congregational minister, Reverend T.Q. Stow, long held a desire to establish in North Adelaide a Congregational church fellowship. He selected the present site and established a building committee. Reverend Dr J. Jefferis was invited to the new pastorate, arriving in Adelaide with his wife in 1859. A hall in Tynte Street was used for worship from the following month and the church was then officially established in North Adelaide. Later that same year a competition for the design of the new church was won by Edmund Wright in partnership with E.A. Hamilton. The building was then described as Greco-ltalian in style to be constructed of bluestone from Dry Creek or Glen Osmond.
On May 15, 1860, the foundation stone (taken from the bed of the River Torrens) was laid. The church design was at this time described as Venetian Ionic in style. The builders were Scott and Opie, and the clerk of works was Thomas Frost, who later became an architect of some note. On February 22, 1861, an incomplete church was opened, with Reverend Stow giving the sermon. The structure, which excluded the lecture hall to the east and tower, was subject to a good deal of adverse criticism due to the “unfashionable” appearance of its stuccoed wall surfaces.
During the 1860s the church became a resort for “enquiring minds professing different creeds or having no settled belief”. Episcopalians, Methodists, Presbyterians, Baptists, Roman Catholics and Jews joined in worship in response to the progressive theology taught under the Reverend Dr J. Jefferis, where “science and philosophy were looked upon as handmaids to religion”.
In 1871, E.A. Hamilton submitted a design for a 107-foot tower. The main body of the church then reached its present form with additional major works to the basement and stables together with railings to the Brougham Place frontages. In 1878 Thomas Frost was commissioned to plan a lecture hall, classrooms and organ gallery, although apparently this work was not completed until after 1880.