První část trati byla vybudována akciovou společností K. k. priv. Ostrau-Friedlander Eisenbahn (Císařsko-královská privilegovaná Ostravsko-frýdlantská železnice) v letech 1869 – 1870 mezi Ostravou a Frýdlantem nad Ostravicí a nesla přiléhavý název Ostravsko-frýdlantská dráha. Tento úsek byl uveden do provozu roku 1871. Druhá část trati, tj. úsek Valašské Meziříčí – Frýdlant nad Ostravicí, byla vybudována roku 1888 jako součást vedlejší větve Severní dráhy císaře Ferdinanda z Kojetína přes Těšín do Bílska. V roce 1885, byla totiž prodloužena koncese Severní dráze (a tím i její monopol na železniční spojení přes Moravu), ale současně jí byla uložena povinnost vybudovat síť paralelních a navazujících tratí. Rakousko-Uherská vláda si totiž uvědomovala, že hlavní spojnice Vídeň – Krakov vede nepříjemně blízko pruského území a v případě další války s Pruskem může být velice rychle přerušena. Severní dráha proto dostala mj. za úkol vybudovat paralelní spojení s Haličí, které bude více ve vnitrozemí. V roce 1887 proto Severní dráha císaře Ferdinanda odkoupila již existující železnice na plánované trase: úseky Kroměříž – Bystřice pod Hostýnem, Valašské Meziříčí – Krásná a Frýdlant – Frýdek. Současně zahájila dobudování úseků Kojetín – Kroměříž, Bystřice pod Hostýnem – Valašské Meziříčí, Krásná – Frýdlant a Frýdek – Bílsko. Stávající úseky byly opraveny a dřevěné mosty byly nahrazeny ocelovými. Provoz na celé trati v délce 180 km mezi městy Kojetín – Bílsko byl slavnostně zahájen 1. června 1888 jako tzv. Moravsko-slezská dráha měst. [zdroj]
