The earliest surviving reference is in a manuscript of c. 1130, but excavations made during 1985 uncovered the foundations of a Saxon predecessor, built between the 9th and 11th centuries, from Kentish ragstone and recycled Roman bricks.

The tower was built separately, projecting from the west of the church, and required the carpenter to build a timber platform 16 feet (4.9 m) below ground to support the rubble foundation.

The church was completed in 1679 at a cost of £5,580, including £10 paid to the then still ruined St Paul's Cathedral for rubble.

St Olave's was the burial place of Robert Large, Lord Mayor, mercer and master of William Caxton, in 1440.

Boydell would visit the church pump (built atop the medieval well) at 5 am each morning, place his periwig on top and douse his head from the spout.

The dead were disinterred and their remains moved to City of London Cemetery, Manor Park, the parish combined with that of St Margaret Lothbury, and the furnishings dispersed to several other churches.

This was replaced in 1986 by an office building, in a sympathetic style, designed by the firm of architects Swanke, Hayden, Connell.