První vlak přijel do Olomouce 17. října 1841 po trati Severní dráhy císaře Ferdinanda. Nádraží bylo zřízeno asi 800 metrů severně od dnešního hlavního nádraží, poblíž hostince Na Špici, za řekou Bystřicí, v prostoru dnešních Pavloviček. Samotná stanice byla na dnešní poměry velmi jednoduchá – velká dřevěná hala, později doplněná podélnými přístavbami. Nebyla to tedy žádná monumentální kamenná nádražní budova, jakou si dnes spojujeme s železnicí 19. století. Důvod byl vojenský. Olomouc byla pevnostní město a kolem hradeb platila přísná omezení nové výstavby. Nádraží proto muselo být umístěno mimo opevněný prostor.
V roce 1845 byla železnice prodloužena z Olomouce směrem na Prahu, takže právě kolem roku 1850 už Olomouc nebyla nějakou koncovou stanicí, byla součástí významné dálkové železniční trasy mezi Vídní a Prahou. Současné hlavní nádraží na místě, které známe dnes, vzniklo až v roce 1870.