Samuel Teulon’s ‘mighty church’, as he called it, was built to provide an additional place of worship for the increased population of the Parish of St John caused by the building of new streets between Belsize Park and Hampstead such as Lyndhurst and Thurlow Roads. When in 1864 it was decided to erect a new church the job of architect ultimately fell to Samuel Teulon after Ewan Christian, architect to the Church Commissioners declined the post. The estimated cost of the church was £7,500 and the money was raised entirely by subscriptions and large donations from local people, its prospective congregation.

Work commenced in January 1869 and the church was consecrated within a year on 31 December 1869 by the Bishop of London. Unlike so many Victorian churches which remained uncompleted, St Stephen’s was finished within three years of its consecration with the clock and carillon being installed in 1873. Soon after the completion of St Stephen’s a school was established in the crypt and there has been an educational use of the Church site since it was built.
St Stephen’s is markedly French in outline, with steep roofs and a massive square tower. When Teulon was first offered the commission, he had particularly requested that the church should be built of brick. For the exterior, he chose brick from Dunstable, which when new was described as varying in colour from pale grey to Indian red giving the church a mottled appearance. The decorative stone bands on the exterior were of Kentish Rag from Maidstone and as if to contrast the exterior, the inside walls were faced with grey, tallow and white bricks from Huntingdonshire laid in stripes and panels. The most spectacular ornamental brickwork was to be found under the tower and in the transepts and is slightly Moorish in style. In addition the sculptural and mosaic decoration was unusually rich and varied, much of which was created by Thomas Earp and Salviati.