The abbey was founded by the Sponheim count Engelbert I, Margrave of Istria since 1090, on the site of a former castle and a church consecrated by Archbishop Hartwig of Salzburg in 991.

A follower of Pope Gregory VII and Archbishop Gebhard of Salzburg in the Investiture Controversy with Emperor Henry IV, Engelbert had forfeited his county in the Tyrolean Puster Valley but could retire to the Carinthian estates his father Siegfried I of Spanheim had acquired through his marriage with the local aristocrat Richgard.

He returned to Carinthia with twelve Benedictine monks from Hirsau Abbey, who received the church and monastery of St. Paul's on 1 May 1091, together with large estates in the Lavant Valley, in the March of Styria and in Friuli.

The ecclesiastical reservation was renewed by Pope Innocent II, who decreed the abbey's exemption in 1140, while the Sponheims, ruling Dukes of Carinthia since 1122, served as Vogt protectors.

In the 16th century, large parts of Carinthia turned Protestant and two abbots were declared deposed by Archduke Charles II of Inner Austria.

After a fire in 1367 a Gothic vaulted ceiling was added, painted with 44 frescoes by the Tyrolean masters Friedrich and Michael Pacher.