Seit 1150 ist Maria Trost in Fernitz ein Wallfahrtsort und zählt damit zu den ältesten der Steiermark. Eine erste romanische Kapelle wurde um 1160 errichtet.

Da der Zustrom an Wallfahrern zunahm, wurde 1314 eine Kirche im hochgotischen Stil erbaut, von welcher noch zwei Geschosse des Turmes an der Nordseite des heutigen Baus erhalten sind.

Das bestehende spätgotische Bauwerk wurde von 1506 – 1514 erbaut und verdankt seine Entstehung vermutlich dem Drängen des in Graz residierenden Kaisers Friedrich III. Als 1480 die drei “Gottesplagen” (Türken, Heuschrecken und Pest) über das Land hereinbrachen, lautete dem Volksmund zufolge das Gelöbnis: “Maria in der Fern…, hilfst du mir, so helf ich dir gern!”. Unter anderem weist der Reichsadler über dem Eingangsportal auf den Kaiser als Bauherrn hin.

Der heutige Bau wurde von derselben Bauhütte errichtet wie der Grazer Dom und sein 68 Meter hoher Turm ist weithin sichtbar.