Auf einer Urkunde des Konzils von Worms vom 16. Mai 868 ist die Gründung eines Damenstifts durch Bischof Luithard von Paderborn und dessen Schwester Walburga "im Gebiet von Heerse" beschrieben. Walburga wird die erste Äbtissin des Stiftes. Am 17. Juni 871 nimmt Ludwig der Deutsche die Neugründung ausdrücklich unter seinen Schutz und gewährt kaiserliche Privilegien. Das Necrologicum Heriense weiß am 6. November (wohl 887 unter Bischof Biso) von einer Weihe der vermutlich ersten Stiftskirche auf den Titel der Gottesmutter Maria - und am folgenden Tag von der Ankunft der Reliquien der hl. Saturnina zu berichten. Papst Stefan V. bestätigte die Gründung am 23. Mai 891 in einer heute noch erhaltenen Papst Urkunde auf Papyrus geschrieben.

Die Gründung in Neuenheerse war zunächst ein Stützpunkt zur Festigung des neuen, christlichen Glaubens im Gebiet der Sachsen. Es handelte sich um eine Familienstiftung, denn Luithard und Walburga hatten dafür ihre Familienbesitzungen eingetauscht. In das Stift aufgenommen werden konnten adelige, unverheiratete Damen. Sie hatten als wesentliche Verpflichtung das Gebet. Zugleich wurde den Jüngeren Stiftsdamen Bildung vermittelt. Nachweisbar ab dem Jahre 1613 war eine Voraussetzung zum Eintritt, daß man seine adelige Herkunft über vier Generationen nachweisen mußte. Im Unterschied zu einem Ordensleben mit Gelübden und strenger Regel war es den Stiftsdamen unter Aufgabe ihrer Präbende möglich, das Stift zu verlassen und dann auch eine Ehe einzugehen. Bis an die Schwelle des 14. Jahrhunderts ist wohl auch noch eine gemeinsame Lebensweise in einer Klosteranlange (die vermutlich südlich der Kirche angebaut war) anzunehmen. Später lebten die Stiftsdamen in separaten Häusern, von denen noch einige in der Ortschaft erhalten sind. Die Zahl der Stiftsdamen schwankte zwischen 10 und 20 Frauen. Bei der Aufhebung waren es zwölf. Alle Stiftsdamen und die beiden Pastöre von Neuenheerse hatten Sitz und Stimme im Kapitel. Die Leitung lag in der Hand der Äbtissin. Sie war geistliches und weltliches Oberhaupt im Stift. Die Pröpstin vertrat das Stift nach außen und die Dechantin hatte für ein geordnetes geistliches Leben innerhalb des Stiftes zu sorgen. Des öfteren wurden seitens der Bischofskirche Versuche unternommen, die Verfassung des Stiftes in eine benektinische Klosterordnung umzuwandeln. Allerdings blieben diese Versuche aufgrund der alten, verbrieften Rechte erfolglos.

In den folgenden Jahrhunderten gelangte das Stift als adeliges Damenstift zu großem Reichtum und Einfluß. Von den reformatorische Ideen blieb es weitgehend unberührt aufgrund der inneren Reformbemühungen der Äbtissinnen Magareta von Columna (1534 - 1589) und Othilie von Fürstenberg (1589 - 1621). Während des Dreißigjährigen Krieges verarmte das Stift durch Schutzgeldzahlungen und Plünderung, wovon sich das Stift erst unter Agatha von Niehausen am Beginn des 18. Jahrhundert erholte. Trotz des Reichdeputationshauptschlusses vom 25. Februar 1803 wurde das Stift zunächst nicht aufgelöst, sondern in eine Versorgungsanstalt für "bedürftige adelige weibliche Personen" aus beiden Konfessionen umgewandelt. Erst durch das Dekret des Königs Jerome von Westfalen vom 01.12.1810 wurde das Stift nach einer fast tausendjährigen Geschichte aufgelöst und die Güter eingezogen. Eine der letzten Stiftsdamen war Sophie von Haxthausen, eine Tante der Dichterin Annette von Droste-Hülshoff, die in ihrer Jugend des öfteren im Stift geweilt hat und Heerse in der "Judenbuche" erwähnt. Die Kirche wurde nach Aufhebung des Stiftes der katholischen Pfarrgemeinde übereignet. Die Bauerhaltungpflicht übernahm mit Einzug der Güter der Fiskus.