Plans for the church were drawn up in 1858, and construction took place between 1860 and 1861 to a design by George Frederick Bodley. Bodley was also working on St. Paul’s Church in West Street, Brighton at the time, on an interior alterations project. The exterior was in red brick with horizontal bands of white stone and a steeply pitched slate roof. This featured a modest flèche spire containing a bell recovered from Sevastopol during the Crimean War.
The church took two years to build at a cost of £6,728, and was consecrated by the Bishop of Chichester on 29 September 1862. However, this fine building quickly became too small and, in 1865, William Burges designed a parallel church which would incorporate Bodley’s building as its south aisle. The rebuilding was not carried out until 1893, and took two years. Burges was a contemporary of Bodley; both men were born in 1827. It is not known for certain why a different architect was chosen for the redesign, and the changes reportedly caused Bodley some upset. Burges did not live to see his designs realised; he died in 1881.
The exterior decoration of the new building broadly matched that of the original church, consisting of bands of white stone contrasting with dark red brick, but there is a considerable difference in height. The original building’s north aisle was demolished, and its remaining structure became the south aisle of the new church. In terms of the church’s present arrangement, therefore, the main body and the adjacent north aisle date from 1893, while the south aisle is original.