It was built between 1839 and 1841 in a simple early Victorian style (to a design by Norwich architect John Brown), replacing an earlier church which had been built on the foundations of the older mediaeval church nearby dating to around 1120.

On completion of the restoration, the church is one of the best preserved examples of a decorated gothic revivalist interior in London.

The ruins of the original building are in the medieval churchyard on the north side of Lee Terrace.

The tomb of Edmond Halley (1656–1742), from 1720 England's second Astronomer Royal and the discoverer of the periodicity of Halley's Comet is in the churchyard,[2] one of three Astronomers Royal buried at St. Margaret's (Nathaniel Bliss and John Pond are the others).

James Annesley, a celebrated claimant to the Earldom of Anglesey, was buried in the churchyard in an unmarked grave.