Koroška proga poteka od Maribora - Studenci do Celovca in je bila zgrajena kot del povezave glavne prometne smeri Južne železnice Dunaj - Trst s Tirolsko. Zasebna družba z imenom Južna železnica (Südbahn-Gesellschaft) je v svoji ambiciji, da bi obvladovala vse večje območje, zgradila najprej povezavo na vzhod od Pragerskega do Budimpešte (1860-1861), nato pa je sklenila povezati Nemčijo z Italijo (Kufstein - Innsbruck - prelaz Brenner - Ala (Verona)) in to Brennersko progo povezati s svojim ostalim omrežjem.
V vozlišču Franzensfeste (danes Fortezza v Italiji) se je nanjo priključila Koroška proga iz Maribora. Le-to je Južna železnica prevzela od lokalnih koncesionarjev, ki so imeli dovolj moči le za začetek del. 15. marca 1856 je bil v Celovcu ustanovljen komite za gradnjo, predkoncesija je bila izdana maja 1856, oktobra istega leta pa je komite dobil koncesijo za gradnjo proge Maribor - Beljak - Brixen (Južna Tirolska) z odcepom Beljak - Gorica.
Progo so začeli graditi 18. julija 1857. Otvoritev je bila 31. maja 1863 (Maribor - Celovec), naslednje leto 30. maja 1864 pa do Beljaka. Dolžina proge (Maribor - Celovec) je 126,5 km - od tega poteka 82,152 km po ozemlju Republike Slovenije. Prvo etapo od Maribora do Vuzenice so predali v promet 13. novembra 1862.
