Bereits im späten Mittelalter dürfte der Mühlenstandort am rechtsseitigen Mühlgang - einem früheren Au-Arm der Mur - genutzt worden sein, nachweisbar ist er seit dem 15. Jahrhundert. Zu den frühen Besitzern der Mühle zählt auch das Haus Eggenberg, 1898 wurde die Mühle vom 1848 gegründeten Jüngeren Bäckermühl-Consortium erworben.

Aus dieser Zeit stammten auch die ältesten der nun abgerissenen Industriegebäude, die übrigen Teile der Anlage kamen zwischen 1950 und -70 hinzu. Um 1900 war die Mühle noch als „Rusterholzermühle" bekannt (nach ihrem ehemaligen Besitzer Jakob Rusterholzer), Anfang des 20. Jahrhunderts wechselte die Marienmühle in den Besitz der Grazer Familie Sorger.

1989 stellte die damals größte steirische Mühle - wie in der Folge fast drei Viertel der zu dieser Zeit noch in Österreich existierenden Mühlen - ihren Betrieb ein. Das verbleibende Kleinwasserkraftwerk am Mühlgang wurde und wird auch weiterhin von der Marienmühle BetriebsgmbH. betrieben.

Neben dem Kraftwerk bleibt die Parkanlage des ehemaligen Mühlareals erhalten. Hier findet sich, angrenzend an die Gebäude des südöstlichen Nachbargrundstückes ein Pavillon des 1943 hingerichteten Grazer Architekten Herbert Eicholzer.

„Herbert Eichholzer ist einer der Kristallisationspunkte im Bereich der ,anderen Steiermark`, die im Faschismus zerschlagen wurde und bis heute - ein später Sieg Hitlers - weitgehend dem Vergessen anheim gefallen ist." So Günter Eisenhut. Herbert Eichholzer wurde am 31. Jänner 1903 in Graz geboren, studierte Architektur und arbeitete u.a. als Volontär bei Le Corbusier und Jeanneret in Paris. Als Architekt erhielt Eichholzer 1935 gemeinsam mit seinem Kollegen Viktor Badl (der auch den Pavillon am Areal der Marienmühle mitverantwortet) den Staatspreis der Grazer Sezession. 1938 emigrierte er noch am Tag des "Anschlusses" nach Paris. Als Mitarbeiter Clemens Holzmeister wirkte der Emigrant u. a. am Bau des türkischen Parlamentes mit. 1940 ging Eichholzer in die Steiermark zurück, um kommunistische Widerstandsgruppen zu ermitteln und zu koordinieren. 1941 wurde er in Frankreich verhaftet, zwei Jahre später in Wien hingerichtet.

Der Eichholzer Pavillon soll nun unter Denkmalschutz gestellt werden und in Zusammenarbeit mit dem Grazer Denkmalamt restauratorisch wiederhergestellt werden - inklusive einiger erhaltener Möbelstücke, die Eichholzer selbst entworfen hat.

Das Projekt Marienmühle/Rondo von  Architekt Markus Pernthaler verfolgt eine ehrgeizige urbanistische Vision. Ziel ist, den städtischen Umraum am rechten Murufer im Einzugsgebiet des Hauptbahnhofs durch eine städtebauliche Zeichensetzung aufzuwerten, die nicht nur ästhetisch neue Wege beschreitet, sondern auch ihren Benutzern außergewöhnliche Qualitäten zu bieten hat.
Es entsteht ein wohl durchdachter Baukomplex, der Strategien des avancierten städtischen Wohnbaus optimiert und die speziellen Qualitäten des ehemaligen Mühlstandorts nutzt.
Der neue Bau bildet eine dynamische Kurvenform, die durch das optisch bestimmende Element des Projekts - eine vorgespannte transluzente Membran aus Polycarbonatstegplatten- noch unterstrichen wird.

Sie umschließt schützend die erhaltene Parkanlage, vom Mühlgang durchflossen, bildet dieser Grünbereich eine Ruhezone mitten in der Stadt. Zu dieser Ruhezone hin öffnen sich die Wohnungen und Büros mit großen Verglasungen, Balkonen und Loggias.

In der Parkanlage findet sich übrigens auch ein Pavillon, der zu den wenigen erhaltenen Bauwerken von Herbert Eichholzer zählt. Der 1943 hingerichtete Grazer Architekt Eichholzer gilt als einer der wichtigsten Vertreter der modernen österreichischen Architektur aus der Zwischenkriegszeit und als eine Leitfigur im kommunistischen Widerstand gegen den Nationalsozialismus. Der Eichholzer-Pavillon wird in Zusammenarbeit mit dem Denkmalamt renoviert.