In 1883,[2] the Reverend Joshua Greaves was appointed vicar, and found at Harringay a fast-growing housing estate rapidly covering open spaces and fields, but no church building.

[3] The digging of the ground preparatory to building the first permanent church began on Tuesday, 20 May 1890, and the foundation stone was laid by Lady Louisa Wolseley (1843–1920) on Saturday, 31 May 1890.

On 28 June 1892 the ecclesiastical Parish of St. Paul's Harringay was formed out of Holy Trinity Stroud Green, St. Anne's Stamford Hill, and St. Mary's Hornsey.

It was constructed of Peterborough red brick with Bracknell stone dressings, with a chancel, south-east chapel and bell-cot, north vestries, and an aisled and clerestoried nave of six bays with north-west and south-west porches.

The incumbents succeeding him were, in chronological order: Appleton, Warren, Brassel, Cowen, Bond, Barraclough, Lloyd, Seeley, and Martin.

[7] In furnishing the new church there has been a significant investment in late twentieth-century British artworks, with the commissioning of pieces from four British artists who were working at the time of the building's creation, namely: the sculptors Danny Clahane, Stephen Cox, and Anton Wagner, and the furniture maker John Makepeace.

The simple and restrained stone statues of St. Paul and of St. Anthony are by Danny Clahane,[8] while the traditional Walsingham-style, painted wooden figure of the Virgin Mary is by Anton Wagner.

[10] John Makepeace has contributed a one-metre-high alms box, carved from a single piece of solid oak with distinctive deep-ridged ziggurat patterns on all four sides.