In 1846, Reverend Henry Michell Wagner, Vicar of Brighton since 1824, bought the chapel and some surrounding buildings for £3,000, cleared the site and appointed a builder and a designer.

Brighton-based builders Cheesman & Son, as they were known at the time, were chosen to construct the building to a design by R. C. Carpenter: they had worked with Rev.

The exterior of the church consists of knapped flint dressed with Caen stone, a type of limestone also used on the Tower of London.

Inside, as well as a nave and chancel, there are two vestries, an organ chamber and a small "crypt chapel" dug into sloping ground.

[9] St Paul's church opened to the public on 18 October 1848 after approximately two years of building works.

The cost of £12,000 was met by a combination of grants from various bodies and societies, public donations, Henry Wagner himself (£1,475) and other members of his family (£1,263).

)[10] The consecration took place on 23 October 1849, and Arthur Wagner assumed responsibility for the church in 1850 when his father presented its curacy to him in perpetuity.

Wagner's mother, father and aunt are all commemorated in the designs, along with some important members of Brighton's Anglican community and other figures.

Alterations in 1861 included the construction of a narthex at the western end, additions to the rood screen between the chancel and the nave, and a reredos designed by Edward Burne-Jones, whose career as an artist was just beginning at this time.

An illustration of the church, showing the (subsequently abandoned) plans for a more traditional masonry spire design, currently (as of 2009) hangs in the "Fishermen's Vestry".

A London-based firm, James Powell and Sons, designed and constructed an octagonal brass lectern which was later donated to the church anonymously.

Several leading figures within the movement either preached at the church at various times (Henry Manning, John Keble) or were friends and associates of Rev.

The existence of confessionals in the church, which became public knowledge during the 1865 murder trial of Constance Kent (who had confessed her crime to Rev.

Wagner), provoked an intensely hostile reaction nationally as well as locally, with consequences ranging from debates in the House of Commons to an assault on Rev.