Archaeological work has revealed the earliest known traces of Christian burial in Sweden on this site, with radiocarbon dating suggesting a Christian graveyard was already in use in the late 800s. A wooden church, then a stone church built by around the 1040s, preceded the monastery, making it one of the oldest stone churches on Swedish soil outside Skåne.
In 1150 the abbot Henrik arrived from Alvastra with Cistercian monks and began building a Romanesque monastery church modelled on Fontenay in France. A fire in 1234 badly damaged the church, and rebuilding under the patronage of Birger Jarl gave it early Gothic vaulting and a new eastern end, with the choir remodelled with a rounded apse and ambulatory chapels in the manner of Clairvaux. The finely carved sandstone capitals and the west front largely date from this thirteenth-century rebuilding.
The church became a burial place for Swedish royalty, including several kings of the Erik dynasty, each commemorated with sixteenth-century monuments. Most striking is the carved grave slab before the Holy Cross altar, believed to mark the resting place of Birger Jarl, founder of Stockholm, along with his son Duke Erik and his second wife. The authenticity of this grave was investigated archaeologically in 2002.
After the Reformation the monastery passed to the crown, and Danish forces burned the monastic buildings in 1566 during the Nordic Seven Years' War. In the 1640s the church was given by Queen Kristina to Count Magnus Gabriel De la Gardie, who restored it as a family mausoleum from 1668. This work added the church's sturdy buttresses, the bulbous central tower, twin western towers and its Baroque furnishings, including an altarpiece and pulpit carved by Georg Baselaque and Hans Hebel in the 1670s.
Later restorations reflect changing tastes in conservation: nineteenth-century work under Helgo Zettervall aimed to recreate a stylised medieval appearance, while Sigurd Curman's more conservative restoration of 1918–1923 deliberately preserved traces from different periods, and uncovered the foundations of the old monastery buildings alongside the church.
Today the church is also linked to the Klosterstaden Varnhem visitor attraction, which grew from interest generated by Jan Guillou's historical novels about the Knight Templar Arn; although the literary connection has faded somewhat, the church remains one of the most visited in Sweden.