The church is dedicated to Alfege (also spelt "Alphege"), Archbishop of Canterbury, and reputedly marks the place where he was martyred on 19 April 1012, having been taken prisoner during the sack of Canterbury by Danish raiders the previous year. The Danes took him to their camp at Greenwich, and killed him when the large ransom they demanded was not forthcoming.
The church was rebuilt in around 1290. It was in this building that Henry VIII was baptised in 1491.
The patronage of the church was given to the abbey at Ghent during the 13th century. Following the suppression of alien priories under Henry V, it was granted to the priory at Sheen with which it remained until transferred to the Crown by exchange under Henry VIII in 1530.
During a storm in 1710 the medieval church collapsed, having had its foundation weakened by burials both inside and outside.
Following the collapse of the medieval church, the present building was constructed, funded by a grant from the Commission for Building Fifty New Churches, to the designs of Nicholas Hawksmoor, one of the commission's two surveyors. The first church to be built by the commissioners, it was begun in 1712, and basic construction was completed in 1714; it was not, however, consecrated until 1718.
The church is rectangular in plan with a flat ceiling, and a small apse serving as a chancel. The east front, towards the street, has a portico in the Tuscan order, with a central arch cutting through the entablature and pediment – a motif used in Wren's "Great Model" for St Paul's Cathedral. A giant order of pilasters runs around the rest of the church: a feature Kerry Downes suggests may have been added by Thomas Archer, who, according to the minutes of the commission, "improved" Hawksmoor's plans. On the north and south sides of the church wide projecting vestibules rise to the full height of the building, with steps leading up to the doors.
Hawksmoor planned a west tower, in the position of the existing one, which had survived the collapse. However the commission was reluctant to fund it, and the medieval tower was retained. In 1730 John James refaced it, and added a spire. Hawksmoor's design, published in an engraving in 1714 had an octagonal lantern at the top, a motif he was later to use at St George in the East.
An organ, built by George England, was installed in the mid-18th century.
During the Blitz on 19 March 1941, incendiary bombs landed on the roof causing it to collapse, burning into the nave. The walls and the tower remained standing, but much of the interior was gutted. The church was restored by Sir Albert Richardson in 1953.