Das genaue Gründungsjahr ist unbekannt. Klar ist nur, dass die Anfänge im 9. Jahrhundert liegen. Vermutet wird eine Gründung zwischen 804 und 860. Damit ist es das zweitälteste Frauenkloster in Westfalen. Als Gründerin des Stifts gilt Emhildis, die vermutlich aus der Ricdagsippe stammte, aus der die Familie der späteren Grafen von Werl hervorging. Urkundlich erwähnt wird ihr Name allerdings erst im 12. Jahrhundert. Sicher ist, dass das Stift eng mit der Familie der Grafen von Werl und später von Arnsberg verbunden war. Sie waren wohl die eigentlichen Stifter. Die Äbtissin kam meistens aus dieser Familie und die Grafen waren bis zu ihrem Aussterben 1368 die Erbvögte des Klosters. Aus der Familie stammten nach 1310 auch einige Pröpste des späteren Kanonikerstifts.
Die erste sichere Erwähnung des Klosters stammt erst von 913. In einer Urkunde bestätigt Konrad I. den Bewohnerinnen des Klosters frühere Privilegien. Dazu gehören die Immunitätsrechte und die freie Wahl der Äbtissin. Für die Bedeutung der Gemeinschaft sprechen verschiedene Schenkungen hoher Adeliger bis hin zu den ottonischen Kaisern. So gewährte König Otto I. dem Stift Zoll- und Marktrechte. Kaiser Otto III. schenkte dem Kloster den Haupthof zu Stockhausen, zu dem etwa 20 weitere Hofstellen gehörten. Diese und ähnliche Schenkungen sowie das Vermögen der Stiftsdamen, das nach deren Tod an die Gemeinschaft fiel, führten dazu, dass das Stift Meschede einen beträchtlichen Grundbesitz und Reichtum ansammelte. Insgesamt hatte es 400 Höfe unterschiedlicher Größe, davon allein 200 im oberen Sauerland. Ein Zeichen für den Wohlstand war, das Äbtissin Hitda dem Stift ein kostbares Evangelienbuch, den heute nach ihr benannten Hitda-Codex schenken konnten. Für die Bedeutung des Stifts spricht auch, dass die Kölner Erzbischöfe ihm mehrere Pfarreien mit deren Besitz und Einkünften unterstellten, so 1042 Calle. Auch das Dekanat Engern (das später in die Dekanate Meschede und Wormbach unterteilt wurde) unterstand seit 1070 der Mescheder Äbtissin. Im Stift lebten neben der Äbtissin etwa 20 Damen. Während die Vorsteherin meist aus dem höheren Adel stammte, kamen die Damen meist aus dem Landadel.
Das Kloster war anfangs Maria geweiht und wurde später ein Zentrum der Verehrung der Heiligen Walburga, deren Reliquien
durch die Vermittlung König Konrads I. zwischen 911 und 918 nach Meschede gelangten.
Die anfänglich starke Stellung der Äbtissin wurde im Laufe der Jahrhunderte zu Gunsten der Stiftsdamen etwas eingeschränkt. So wurde im 12. Jahrhundert bei der Güterverwaltung ein Konsens zwischen Äbtissin und Konvent üblich. Abgesehen von der Rolle bei der Christianisierung in den ersten Jahrhunderten des Bestehens spielte das Stift eine wichtige Rolle für Kultur und Bildung. Es gab eine Schule für Jungen, insbesondere für diejenigen die in den geistlichen Stand eintreten wollten und eine Urkunde von 1177 deutet auch eine schulische Ausbildung für weibliche Jugendliche an. Für die Seelsorge gab es einen eigenen Konvent von zehn Kanonikern.
In den folgenden Jahrhunderten verlor das Stift allerdings durch einen wirtschaftlichen Niedergang an Bedeutung. Als problematisch erwiesen sich der weit verstreute Besitz und die allmähliche Ablösung der Naturalabgaben durch Geldleistungen. Da diese nicht der Teuerung angepasst werden konnten, sank de facto das Einkommen des Stifts ab. Hinzu kam, dass im Laufe der Zeit die abhängigen Bauern sich als Besitzer betrachteten und die Zahlung einstellten. Es gab auch Kritik an Verweltlichung der Stiftsdamen.