Gradnja proge Celje–Ljubljana je bila zaradi ozkega prostora v dolini rek Savinje in Save izjemno zahtevna in zamudna. Na trasi med Celjem in Zidanim Mostom so zgradili štiri mostove in še enega v Zidanem Mostu, kjer je proga prečkala Savinjo in šla na levi breg Save.
Prostor za progo in pripadajoča železniška poslopja so si večkrat izborili z razstreljevanjem skalovja, zaradi nevarnosti plazov in padajočega kamenja pa so morali velik del proge zavarovati z betonskimi plombami in s palisadnimi stenami.
Sredi težavne gradnje so leta 1848 z Dunaja prispele novice o izbruhu marčne revolucije, katere vpliv je bilo mogoče čutiti tudi v narodnostno pisani množici delavcev na gradbiščih. Neredi v monarhiji so povzročili zatikanje pri financiranju in strah, da proga še leta 1849 ne bi bila dograjena, zato je oblast izdala nalog, naj se dela pospešijo. To je dalo gradnji nov zagon in 18. avgusta 1849, na rojstni dan cesarja Franca Jožefa, je iz Celja v Ljubljano pripeljala prva lokomotiva.
