Den Baubeginn der Kirche soll angeblich Heinrich II. nach seiner Krönung zum König Anfang Januar 1003 veranlasst haben. Die Kirche entstand zunächst als Massivbau aus Kalkstein und einer turmlosen vorromanischen Basilika mit einfacher Apsis, die der Mutter Jesu, Maria, geweiht wurde.
Die erste Erweiterung veranlasste Bischof Bruno von Würzburg an Ostern 1034. Mit der Errichtung eines Chores und eines Querschiffes bekam das Kirchenschiff die Form eines Kreuzes, welches auch als "Kreuzschiff" bezeichnet wird. Die Bauarbeiten zogen sich bis in das Jahr 1045 hin. Nach dem Jahre 1100 begann man an der Westfront der Kirche mit dem Aufbau der beiden Türme und an der Südseite mit dem Aufbau der Marienkapelle.
Die Marienkapelle sowie das Dach der Kirche wurden am 3. Juni 1175 durch einen Blitzschlag zerstört. Nach der Vollendung der Erweiterungsbauten weihte am 7. Juni 1278 der Würzburger Bischof Berthold II. von Sternberg die romanische Kirche zum zweiten Mal auf den Namen "Unserer lieben Frauen".
Im Jahre 1296 zerstörte wiederum ein Blitzschlag den Glockenturm nebst Glocke und das Kirchendach. Dabei ging auch die neu erbaute Marienkapelle wieder verloren.
In den Jahren 1443 bis 1455 entstand der bis heute bestehende gotische Chor in weitaus größerer Dimension als das weiter bestehende romanische Langhaus.
Die Grafen von Henneberg führten im Jahre 1544 die Reformation im Henneberger Land durch und die Stadtkirche wurde evangelisch.
Die erste Orgel erhielt die Stadtkirche 1546, welche man in den Chor statt wie üblich an der Westwand einbaute. Die Orgel stammt aus der Klosterkirche des Meininger Franziskanerklosters, das nach der Reformation aufgelöst wurde.
Neben dem kirchlichen Alltag und der Funktion als Pfarrkirche finden in der Stadtkirche Musikveranstaltungen mit Chören, Folkloregruppen, verschiedene Musikstile ausübende Musiker oder Orgelkonzerte statt. Darunter befindet sich auch der alljährlich stattfindende "Meininger Orgelsommer". Auch werden regelmäßig Ausstellungen und Sonderaktionen mit kirchlichen Themen in der Kirche durchgeführt.