Auf Bitten seines Sohnes Otto, der in der burgundischen Zisterzienserabtei Morimond das Ordenskleid genommen hatte, entschloss sich Markgraf Leopold III. (reg. 1095-1136) um 1133 zur Stiftung eines Zisterzienserklosters im südlichen Wienerwald, das von Anfang an, und nicht erst seit dem Erhalt der großen Kreuzreliquie im Jahr 1187, Sancta Crux, Heiligenkreuz, genannt wurde.
Im 12. und 13. Jahrhundert erlebte das Stift eine erste Blütezeit: So wuchs in dieser Zeit der klösterliche Besitzstand rasch an, wobei sich neben der babenbergischen Herrscherfamilie und den ungarischen Königen auch zahlreiche Adelige und Bürger als Gönner hervortaten. Der damalige Aufschwung spiegelt sich aber auch in der bis zum heutigen Tag erhaltenen eindrucksvollen mittelalterlichen Klosteranlage wider, die aus dem 12. und 13. Jahrhundert datiert: 1187 wurde der romanische Kirchenbau geweiht, 1220-1240 die Klosteranlage frühgotisch umgebaut, 1295 der gotische Hallenchor und das Brunnenhaus vollendet.
An der Filiationstätigkeit des Wienerwaldklosters werden dessen Personalressourcen erkennbar: Heiligenkreuzer Mönche besiedelten innerhalb von zwei Jahrhunderten sieben weitere Zisterzienserabteien, namentlich Zwettl (1138), Baumgartenberg (1142), Czikador (1142), Marienberg (1197), Lilienfeld (1202), Goldenkron (1263) und Neuberg (1327). Schließlich ist auch auf die Leistungen der Mönche auf kulturellem Gebiet zu verweisen: Abgesehen von der Produktion wertvollster Handschriften (bis 1230 ist die Entstehung von 54 Codices in der Heiligenkreuzer Schreibstube nachweisbar) sind in diesem Zusammenhang vor allem die wissenschaftlichen Leistungen einiger Mönche zu nennen, die, wie etwa Gutolf von Heiligenkreuz, zu den bedeutendsten Köpfen ihrer Zeit zählten.
Das spätere Mittelalter stellte Heiligenkreuz vor vielfältige Herausforderungen. Schon seit dem 13. Jahrhundert nahm die Zahl der Heiligenkreuzer Mönche, nicht zuletzt aufgrund des Aufschwungs der Bettelorden in den Städten, stark ab. Aber auch die große Pestepidemie in den 1340er-Jahren dezimierte den Konvent. Auch litt das Kloster schwer unter den politisch wechselhaften Zeiten. Durch die ständigen Kriege und durch die Auseinandersetzungen im Haus Habsburg stand das Stift mehrmals am Rande des Ruins. Fehden nahmen überall überhand. Söldnerbanden suchten Heiligenkreuz und seine Besitzungen heim. Hungersnöte brachen aus, weil die Ernte durch das kriegerische Treiben vernichtet oder nicht eingebracht werden konnte. Eine arge Inflation tat das Übrige. Erst im ausgehenden 15. Jahrhundert beruhigte sich die Situation ein wenig. Doch auch die Folgezeit brachte keine echte Besserung der Lage.
Sehr zu leiden hatte das Kloster unter den Türkenkriegen von 1529 und 1532. Und auch die aufkommende Reformation stellte den Konvent vor so manches Problem. Nicht wenige der Mönche verließen damals Kloster. Personell stand es in den 1540er-Jahren vor dem Aus. Doch wendete sich das Blatt mit dem Abbatiat Konrad Schmids (1547-1558), unter dessen Leitung eine Phase der personellen, wirtschaftlichen und kulturellen Konsolidierung eingeleitet wurde, die unter seinen Nachfolgern Abt Ulrich Müller (1558-1584) und Abt Johann Rueff (1585-1599) eine Fortsetzung fand.
Die so bald wieder gefestigte Stellung des Stiftes machte auch die Inangriffnahme neuer Aufgaben möglich, wobei in diesem Zusammenhang vor allem auf die Pfarrseelsorge zu verweisen ist: Seit der zweiten Hälfte des 16. Jahrhunderts wurde sie systematisch in Angriff genommen und entwickelte sich bald zu einem zentralen Betätigungsfeld der Mönche.