Although the church was built between 1872 and 1875 and consecrated on 1 May 1875, its founding was closely connected with the former Vicar of Brighton, Reverend Henry Michell Wagner, who had served the town from 1824 until his death in 1870.

[2] When his father died, Arthur Wagner inherited his wealth and set out to build a church both to commemorate him and to fulfil the plans he had towards the end of his life.

)[3] One action the Revd Henry Wagner had taken before his death was the creation of a "building committee", consisting of other prominent members of the local clergy.

The committee decided to allow the Wagners to choose the site themselves; accordingly, a position on the west side of Lewes Road, just north of the bottom of Elm Grove, was selected.

[3] The exterior of St Martin's reflects the Gothic Revival interpretation of the Early English style associated with 13th century churches.

The church floor lies six feet below street level, creating an architectural illusion of being larger internally and from the entrance there is an unimpeded view across the nave and into the chancel.

[6] A series of 144 painted shields adorn the nave ceiling, representing the Anglican missionary dioceses founded within 100 years of the church.

[7] The original pulpit, surmounted by a unique canopy tapering to 55 feet and dating from 1880, also remains: this, and the font in the raised entrance area, are decorated with materials from the collection of Henry Wagner.

A gallery was built on the east side of the chancel for troops and members of military bands to participate in services; also, two different regiments erected memorials to comrades killed in the Siege of Khartoum in 1884 and 1885.