The church was dedicated to St Gregory the Great. It was in existence by 1010, when the body of St Edmund was housed there. The remains of the king, martyred in 870, had been translated to London from Bury St Edmunds by Alwyn, later Bishop of Elmham, for safe-keeping during a period of Danish raids, and were returned there three years later. The patronage of the church originally belonged to the crown, but during the reign of Henry VI it was transferred to the minor canons of St Paul’s.

Between June and November 1571, services were transferred from St Paul’s to St Gregory’s while fire damage was being repaired in the cathedral.

On 19 December 1591, Elizabeth Baldry, wife of the 2nd Baron Rich and mother-in-law to Penelope Devereux, Lady Rich, was buried at St Gregory’s.

The existence of the church came under threat while Inigo Jones was remodelling the cathedral in the 17th century. At first he thought that he could accommodate St Gregory’s in his plans, writing in a report, dated 11 June 1631, that "the church is in no way hurtful to the foundations or walls of St. Paul’s, nor will it take away the beauty of the aspect when it shall be repaired. It abuts on the Lollards’ Tower , which is joined on the other side by another tower, unto which the Bishop’s hall adjoins. Conscious that neither of them is any hindrance to the beauty of the church." Over the next few years the parishioners spent a considerable sum on the fabric of the church: Robert Seymour mentions a sum of more than £2000 being spent in 1631-2, while in 1641 the Journal of the House of Commons recorded that more than £1500 had been spent on beautifying the building "four years since".

By 1641, however, Jones had changed his mind, and decided that his renovation of the cathedral necessitated the removal of St Gregory’s. Once demolition had begun, Jones ordered the parishioners to take down the remainder. According to their account, he threatened that if they did not take down the rest of it, "then the galleries should be sawed down and with screws the materials thrown down into the street." The threat having proved ineffective he said "that if they did not take down the said church, they should be laid by the heels." The parishioners complained to the House of Commons of England, and the Commons passed their complaint on to the House of Lords, appending a declaration that the parishioners deserved redress, and that action should be taken against Jones for the destruction. The Lords decided against Jones and the church was rebuilt using stones intended for the cathedral.

In June 1658, a minister of the church, Dr John Hewitt, a royalist, was executed for high treason. He was beheaded on Tower Hill by order of Cromwell’s high court and buried in the church.

The church and the cathedral were destroyed by the Great Fire of 1666. The church was not rebuilt; the parish was instead united with that of St Mary Magdalen Old Fish Street.