In the Late Middle Ages, Waltham was one of the largest church buildings in England and a major site of pilgrimage; in 1540 it was the last religious community to be closed during the Dissolution of the Monasteries.

[4] Traces of the flint rubble foundations of a 7th-century wooden church have been found under the choir of the present building; an associated burial has been radiocarbon dated to between 590 and 690.

[6][incomplete short citation] During the reign of King Offa of Mercia, whose rule extended to the Kingdom of Essex in the late 8th century, a building of Barnack stone was constructed around the earlier wooden church.

A legend, recorded in the 12th-century De Inventione Sanctœ Crucis Nostrœ ("The Discovery of our Holy Cross") or "Waltham Chronicle", relates that, in about 1016, the blacksmith at another estate belonging to Tovi, at Montacute near Glastonbury, found a large black flint (or marble) crucifix buried at the top of a hill, after a dream.

Tovi had the cross loaded onto an ox-cart, but the oxen would only go in one direction and continued every day until they reached Waltham, a journey of some 150 miles.

Evidence suggests that stone and some of the foundations of the previous church were re-used for the new building, which had a nave the same length as the present one, aisles, a large transept and a small eastern apse.

Although there is a marked stylistic resemblance to Durham Cathedral, a recent study of the features of the church and comparison with other sites has concluded that the master mason at Waltham was trained in East Anglia.

[15] In 1177, the abbey was re-founded once more, this time as an Augustinian priory with 16 canons, by Henry II as part of his penance for the murder of Thomas Becket.

[17] The Holy Cross attracted many pilgrims and the Abbey became a popular place for overnight stays for kings and other notables hunting in Waltham Forest.

[20] On 23 March 1540, the last abbot, Robert Fuller, surrendered the abbey and its estates to Henry's commissioners, the annual income from which was valued at £1,079, 12 shillings and one penny.

The restoration was extensive; the removal of pews and galleries from the south and west sides, a new ceiling (painted with signs of the zodiac as at Peterborough Cathedral), a new chancel and significant re-building.

[29] The Abbey's stained glass includes early work by Edward Burne-Jones in the rose window and lancets of the east wall, and Archibald Keightley Nicholson in the Lady Chapel.

[citation needed] In April 1941, a 500 kg German parachute mine exploded in a field nearby at Romeland, destroying most of the windows on the north side of the church.

[31] Harold stopped to pray at Waltham on his way south from the Battle of Stamford Bridge to fight William of Normandy; the battle-cry of the English troops at Hastings was "Holy Cross".

[32] William of Malmesbury wrote in the Gesta regum Anglorum in 1125, that the refusal to accept Gytha's gold simply meant that Harold's body was handed over without payment, and that it was taken from the battlefield to Waltham for burial.

After the battle, they asked permission to recover Harold's body, which could only be identified by his concubine, Edith Swanneck, who recognised "secret marks".

that the motive for this was to distract attention away from Harold's tomb in the church, as he was still a politically sensitive figure to the Norman ruling class.

In the 18th century, the historian David Hume wrote that Harold had been buried by the high altar in the Norman church and moved to the choir of the later Augustinian abbey.

Visitors were shown a stone slab bearing the inscription "Hic iacet Haroldus infelix" ("Here lies Harold the unfortunate"), although it had been destroyed when that part of the abbey was demolished at the Dissolution.

In his description of Essex, Defoe mentions Waltham Abbey where "the ruins of the abbey remain; and tho’ antiquity is not my proper business, I cou’d not but observe, that King Harold, slain in the great battle in Sussex against William the Conqueror, lies buried here; his body being begg’d by his mother, the Conqueror allow’d it to be carried hither; but no monument was, as I can find, built for him, only a flat grave-stone, on which was engraven, Harold Infoelix.

The Herald Angels Sing" was first heard sung to a melody from Felix Mendelssohn's Festgesang in the church on Christmas Day 1855 with William Hayman Cummings, who made the adaptation, at the organ.