Um 1230 erfolgte erstmals die urkundliche Nennung eines Frauenklosters als »novella Plantatio in Vrundeberg«. Unter Führung des Kölner Erzbistums förderte Otto von Altena, der Bruder des regierenden Grafen von der Mark und gegen diesen gerichtet, ab Mitte des 13. Jahrhunderts den Bau der Kirche (Patrozinium Maria und Mauritius). Beteiligt an der Fundation waren einer späteren Überlieferung zur Folge auch die Edelherren von Ardey und das Arnsberger Grafenhaus. Unter Ottos Neffen, Graf Eberhard II. von der Mark, wurde nach 1288 weiter gebaut und die Kirche bis Mitte des 14. Jahrhunderts vollendet. Als Zeichen uneingeschränkter Territorialherrschaft gegenüber kurkölnischen Ansprüchen wurde in der Klosterkirche die Grablege für Eberhard II. von der Mark und seine Nachfolger eingerichtet. Der Konvent bildete sich über etwa 200 Jahre aus Töchtern bürgerlicher Familien umliegender Städte unter Leitung einer adeligen Äbtissin. Das Schutz- und Vogteirecht blieb bis 1391 bei den Grafen von der Mark, ging dann an das klevische Herzogshaus, später an das Haus Brandenburg (ab 1701 Preußen) über. In der Klosterzeit war ein Gnadenbild der Jungfrau Maria im weiten Umkreis ein Pilgerziel. Ab Ende des 15. Jahrhunderts und begünstigt durch die Reformation wandelte sich das Kloster in Abkehr vom Regelwerk des Zisterzienserordens zum freiweltlich-adeligen Damenstift.
1550 ist nur noch vom adeligen Stift die Rede, besiedelt von katholischen Damen aus dem Sauer- und Münsterland, lutherischen Damen aus der Mark und reformierten Damen vom Niederrhein. Nur in den Grafschaften Mark und Ravensberg gab es einige Stifte, die dauerhaft mehrkonfessionell geprägt waren. Ab dem 17. Jahrhundert war die Zahl der Versorgungsstellen auf 24 beschränkt, die ihre Versorgung aus den Einkünften von Bauernhöfen in der näheren und weiteren Umgebung erhielten.
Gelockerte Präsenzpflichten, zeitliche Gelübde, eigene Haushalte und Verringerung der Gebets- und Gottesdienstzeiten kennzeichneten den Wandel vom Kloster zum Stift. Ab dem frühen 17. Jahrhundert entstanden repräsentative stiftische Gebäude, die ehemalige Klostergebäude ersetzten. Eine Doppelpforte und Reste des Kreuzgangs erinnern noch an die Klosterzeit.
Erst spät bildeten sich eigenständige Kirchengemeinden für die Bewohner Fröndenbergs außerhalb der Stiftsimmunität und die vom Konvent besoldeten Stiftsgeistlichen wuchsen hinein in die Rolle von Gemeindepfarrern.
1812 wurde das Stift aufgelöst, jedoch die Kirche, die bis heute unter Staatspatronat steht, als Gottesdienstort von allen drei Konfessionen weiterhin simultan genutzt. 1837 vereinigten sich Reformierte und Lutheraner. 1895 erbaute die katholische Gemeinde ein eigenes Gotteshaus.
1903 erhielt die Kirche einen Glockenturm.
Hervorzuheben ist ein Altarretabel aus der Schule des Conrad von Soest aus dem frühen 15. Jahrhundert und die Bader-Orgel von 1692.