Erzherzog Johann war es,  der früh die Bedeutung der eben in England entwickelten Eisenbahn erkannte. Schon 1816 hatte er mit Fachleuten bei einem Englandaufenthalt Grubenbahnen, Lokomotiven und Dampfschiffe in einer Art Werkspionage besichtigt. Ab 1825 trat dann der steirische Prinz energisch für eine Eisenbahnverbindung zwischen Donau und Adria ein, um die Hauptstadt des Reiches mit dem wichtigsten Hafen zu verbinden.

Carl Ritter von Ghega © KK Südbahn über Ungarn 1828 projektierte der Grazer Techniker Franz Xaver Riepl eine Bahnverbindung von Galizien über Wien nach Triest – über Westungarn und die Südsteiermark. Denn der Semmering galt als unüberwindbares Hindernis. Hätte man Riepls Pläne wirklich umgesetzt, wäre dies ein enormer Nachteil für die Ober- und Mittelsteiermark geworden, auch Graz wäre nicht an der Schnellverbindung gelegen. Da musste etwas geschehen.

Erzherzog Johann vertraute der modernen Technik und war fest davon überzeugt, dass es in absehbarer Zukunft möglich sein würde, mit der Eisenbahn auch hohe Berge zu überwinden. Also setzte er all seinen Einfluss in Wien ein, damit die Südstrecke über Semmering, Mürzzuschlag, Bruck und Graz nach Triest geplant wurde.

Auch die steirischen Stände waren an der neuen Trassenplanung sehr interessiert, stellten dafür sogar 14.000 Gulden bereit und verpflichteten sich, auch alle Grundablösen durchzuführen. Mit vereinten Kräften konnte sich die steirische Lobby durchsetzen. 1842 war der erste Teilabschnitt von Wien nach Gloggnitz fertig, an eine Trasse über den Semmering wagte man sich aber noch nicht. Hier verkehrten nach wie vor Fuhrwerke und Pferdekutschen, in welche die Passagiere umsteigen mussten.

Erst ab Mürzzuschlag wurde die Eisenbahn unter Leitung des Staatseisenbahninspektors Carl Ritter von Ghega bis Graz weitergebaut wobei die Trassenführung dem Mürz- und Murtal folgte.

Die Anekdote erzählt, dass die Vermessung der Eisenbahnstrecke ergab, dass die Schienen mitten durch den Stall eines Mürztaler Bauern führen würden. Der hatte dagegen überhaupt nichts einzuwenden, bloß die Züge dürften nur bis Einbruch der Dunkelheit verkehren, meinte er – weil dann müsse er seinen Stadl wieder zusperren.

Die Badlwand-Galerie Besonders kompliziert gestaltete sich die Projektierung der Strecke durch die Murenge bei Peggau, in der Ghega die spektakuläre Badlwand-Galerie errichten ließ. Die steilen Felswände wurden durch italienische Arbeiter von oben herab fast senkrecht händisch abgearbeitet.

Bis zu 1500 Mann hingen gleichzeitig in der Wand, bohrten Löcher und legten Minen. In nur 66 Bauwochen wurde die 94,7 Kilometer lange Strecke fertiggestellt, und am 21. Oktober 1844 konnte die Strecke Mürzzuschlag – Graz feierlich eröffnet werden. Die erste Fahrt dauerte exakt drei Stunden und 21 Minuten. Dann wurde der Ausbau der Strecke nach Süden vorangetrieben. 1846 wurde Cilli erreicht, 1849 Laibach. Noch immer aber klaffte am Semmering die lästige Lücke in der Bahnstrecke, die zwischen 1848 und 1854 nach den Plänen Ghegas endlich fertiggestellt wurde und heute als erste Hochgebirgsbahn der Welt berühmtes Weltkulturerbe ist.

1857 wurde dann das letzte Teilstück von Laibach nach Triest gebaut. Die neue Bahn schloss die Steiermark an die weite Welt an, hatte aber auch für Graz stadtplanerische Folgen: Die Murvorstadt erlebte einen Aufschwung. Zwei neue, gerade Straßen verbanden die Stadt mit dem Bahnhof – die Annenstraße und die Keplerstraße.

Von 1843 bis 1847 war der Bahnhof gebaut worden, der Südbahnhof genannt wurde: ein 89 Meter langes Aufnahmegebäude mit vorgebauter Personenhalle, hohen Rundbogenfenstern und einem Uhrturm. Insgesamt war das Bahnhofsareal 700 Meter lang, und doch war es bald schon wieder zu klein. Also wurde von 1871 bis 1876 ein Erweiterungsbau im Gründerzeitstil mit vorspringendem Mittelbau, flachen Seitenflügeln und zwei Endpavillons errichtet.