Velenjski premog in šoštanjska tovarna usnja sta v Velenju spodbudila tudi gradnjo železniške proge, najbolj goreč pobudnik pa je bil gotovo Daniel von Lapp, saj je bila prihodnost njegovega premogovnika odvisna od prometnih povezav Šaleške doline s širšo okolico.
Železnica je privabljala naseljence kot magnet, kajti Stara vas in trg sta se začela kmalu širiti ob cesti proti njej. Progo od Celja do Velenja z industrijskim tirom do velenjskega premogovnika v Škalah, skupno dolgo nekaj manj kot 40 km, so uradno začeli graditi 24. aprila 1891, prvi vlak pa je v Velenje pripeljal 27. decembra 1891. Z drugo fazo izgradnje savinjsko-mislinjske železnice, ki je povezala Velenje in Dravograd, so začeli 1897 in jo končali dve leti pozneje. Arhitektura železniške postaje je bila tipizirana za celo Avstro – Ogrsko z značilno rumeno barvo fasade. Postaja je bila opremljena s kurilnico, potniško blagajno in garderobo za prtljago.