Das Kloster Haholdesbrunn wurde 1132 vom Bamberger Bischof Otto I. gestiftet. Nach 1140 errichteten dann Zisterziensermönche ihr Münster als romanischen Bau.
400 Jahre lang bestand der Konvent, in dieser Zeit wurde das Münster mehrfach erweitert:
Kurz vor 1200 errichtete man die Heideckerkapelle (Michaelspatrozinium) als Karnerkapelle (Beinhaus).
1263 – 1284 erfolgte die Ostchorerweiterung im gotischen Stil, nachdem der Konvent sich vergrößert hatte.
Um 1350 wurde im Westteil ein Paradies (Vorhalle) durch die größere Ritterkapelle als Grablege für den fränkischen Adel ersetzt.
1412 -1437 erfolgte die Verbreiterung des südlichen Seitenschiffs zum Mortuarium (Halle für Bestattungen) im spätgotischen Stil.
1427- 1433 wurde der gotische Chorbogen als Unterbau für den neuen, nun steinernen Dachreiter errichtet.
Mit der Einführung der Reformation in den Fürstentümern Ansbach und Kulmbach (Bayreuth) endete das Klosterleben nach dem Tod des letzten Mönchs im Jahr 1578.
Bereits vier Jahre später ließ Markgraf Georg Friedrich die leerstehenden Klostergebäude für eine höhere Schule, Fürstenschule genannt, umgestalten. 100 Knaben aus finanziell weniger gut gestellten Familien in beiden Herrschaftsbereichen sollten hier eine gymnasiale Ausbildung erhalten. Das Münster wurde den neuen Gebräuchen entsprechend leicht verändert. Im Lang- und im Querhaus erhielt es hölzerne Tonnen im Stil der Renaissance, Altäre wurden umgestellt, der Gottesdienstraum in das Langhaus verlegt.
Der Dreißigjährige Krieg brachte Verwüstungen durch räuberische Soldaten mit sich. Die Mitglieder der markgräflichen Familie wurden von nun an nicht mehr im Münster, wie seit 1297, sondern in Ansbach bestattet.
Im Jahr 1700 sind 20 Privatwohnungen in Heilsbronn nachgewiesen, alle Einwohner waren evangelisch-lutherisch. Für sie ließen die beiden Markgrafen (Ansbach und Bayreuth) durch die Architekten Gabrieli, Zocha und Bruckner im Vierungsbereich und im vorderen Langhaus eine „Protestantische Predigtkirche“ errichten. Zwei Mauern wurden bis zur Decke hochgezogen. Eine an der Stelle der vorherigen Chorschranke, heute durch ein Gitter gekennzeichnet. Die andere als barocke „Markgrafenwand“ mit Altar, Kanzel und Orgel übereinander; sie stand im Bereich des heutigen Kreuzaltars. Nur noch drei Objekte aus jener Zeit sind erhalten geblieben: das hölzerne Taufbecken, der stilgleiche Opferstock (heute im Museum) und das Altarbild (heute über der Türe in der Heideckerkapelle – sie zeigt eine Kopie der Kreuzabnahme von Rubens). Von den 29 Altären am Ende der Klosterzeit sind viele während des 18. Jahrhunderts verschwunden, heute befinden sich nur noch neun davon, einige nur in Teilen erhalten, im Münster – allerdings durch Restaurierungen am Ende des 19. Jahrhunderts verändert (neugotische Gesprenge und einige neu geschnitzte Figuren).
Nach der Angliederung Frankens an Bayern im Jahre 1806 kamen Ausstattungsstücke nach München (Löwenuhr, Rahmen des Epitaphs für Georg Friedrich, Pflastersteine u.a.). König Ludwig I. beauftragte 1845 den Architekten Friedrich v. Gärtner mit dem Herausnehmen der barocken Einbauten und der Wiedersichtbarmachung einer romanischen Basilika. Dazu sollten das Mortuarium abgetragen und der gotische Ostchor romanisiert werden. Schließlich wurden jedoch nur die Holztonnen entfernt, die Fenster vergrößert, die Wände verstuckt und milchblau gestrichen. Der Westgiebel und die nördlichen Außenmauern stammen aus dem 19. Jahrhundert, der Dachreiter (Turm) aus dem 20. Durch das neu erwachte Interesse für das Mittelalter in der Zeit der Romantik erfolgte die Restaurierung von fünf teilerhaltenen Altären und deren Neuaufstellung an anderen Orten im Münster. 1945 führten die Amerikaner Sprengungen in einem Munitionslager im nahen Neuendettelsau durch. Als Folge lösten sich Teile des Stucks an den Kirchenwänden, dies führte zu dessen fast vollständiger Abnahme, so dass seither der Sandstein sichtbar ist. Ob die Wände zur Klosterzeit ursprünglich geschlämmt (transparent überstrichen) waren, kann nicht mehr geklärt werden.