Na liniji od Gradca do Celja so izdelali dve varianti. Po prvi naj bi proga do Celja vodila preko Maribora, po drugi pa preko Ptuja in Poljčan. Odločili so se za mariborsko varianto, ki je bila krajša in je vodila po bolj položnem terenu. Ptuj je bil takrat sicer trgovsko prav tako razvit in močan kot Maribor, vendar slednjemu, bodočemu pomembnemu prometnemu križišču, ni bilo mogoče odrekati prednosti. Proga je prečkala številne razvodnice, gradbenikom sta velike izzive predstavljala zlasti prehod čez poplavno ozemlje Pesnice ter premostitev Mure in Drave.
Proga je dosegla reko Voglajno, zato so z zemeljskimi deli začeli tudi v okolici Celja. Takole jih v svoji Celski kroniki za leto 1845 opiše Ignac Orožen: »21. januarja so tu v Zavodni začeli železnico delati. Pervo delo je bilo, da so tamo Voglajni dolj do jezi novi žleb izkopali. Železnico so delali od Gradca do Cela Feliks ino Anton Talachini, od tod do Zidanega mosta pa Joanez Piko, zidarski mojster iz Belaka, ino Liebman, zidarski mojster iz Bruka. Delavcev je toliko prišlo iz Furlanije, Primorja ino Češkega, da jih je vse živo okrog Cela bilo.«
