Na stavbu železnice boli okrem domácich robotníkov, ktorí vykonávali zväčša pomocné práce, povolaní skúsení robotníci z Čiech, Moravy a Nemecka, ktorí už mali skúsenosti so stavbou železníc. Okrem nich prišli i talianski robotníci, odborníci na kamenárske práce, potrebné pri stavbe mostov a tunelov. Podľa výkazu v apríli 1870 pracovalo na stavbe tejto železnice 16 561 robotníkov. Z toho bolo 935 murárov, 2140 tesárov, 482 kamenárov, 738 mínerov, 152 skalníkov a 953 robotníkov iných profesií. Ostatní boli pomocní robotníci.

Železnica bola stavaná ako jednokoľajná. Podľa koncesnej listiny boli koncesionári povinní ju zdvojkoľajniť v tom prípade, ak ročný hrubý zisk na jednu míľu železnice prekročí v dvoch po sebe idúcich rokoch sumu 150 000 zlatých. Čo sa týka stavebno-technickej stránky, koncesia určovala najmenšiu prípustnú šírku železničného zvršku v úrovni koľajníc na 12 stôp (asi 4 m). Pri stavbe tunelov sa požadovala svetlosť na šírku v úrovni koľajníc 14 stôp a na výšku 20 stôp (1 stopa – asi 30 cm). Na stavbu boli použité prevažne koľajnice o váhe 34,5 kg/bm.

Dostatok financií umožnil rýchle napredovanie vo výstavbe železnice. Ešte pred začatím stavby na jednotlivých úsekoch boli urobené úpravy vo vedení trasy. Trasa od roku 1862, keď sa začalo s jej predbežným vymeriavaním, bola viac ráz menená v detailoch i v jednotlivých úsekoch. Ešte v roku 1862 nebolo vyriešené, či trasu viesť od Popradu údolím Čierneho, alebo Bieleho Váhu. V roku 1864 padla voľba na údolie Čierneho Váhu, čo bolo zakotvené i v koncesnej listine. V týchto miestach mala trať prekonávať európske rozvodie pri Šuňave, kde mal byť tunel. Jeho stavba sa však nerealizovala. Preto bola vynechaná nová trasa medzi Spišskou Teplicou a Liptovským Hrádkom, v dĺžke 38 km. V takejto podobe bola o dva roky neskôr uvedená v koncesnej listine. V § 1 sa doslovne uvádza: „Hlavná trať má viesť z Košíc cez údolie Hornádu, cez Obišovce (Kysak) do Popradu, odtiaľto cez Šuňavu údolím Čierneho Váhu do Hrádku a údolím Váhu ďalej do Žiliny a odtiaľto cez Jablunkov, Tešín, Karvinú a Orlov do Bohumína.“ Nakoniec však pri stavbe ani táto trasa nebola dodržaná a trať viedla údolím Bieleho Váhu, teda tak ako teraz. V tomto úseku sa tiež znížilo stúpanie z pôvodného 1:50 na 1:70. V tomto pomere trať neustále stúpala od Spišskej Novej Vsi až po Štrbu.

Úpravy boli robené v dobe, keď sa na iných úsekoch už pracovalo, prípadne boli pred dokončením. Prvým úsekom železnice, odovzdaným do prevádzky na Slovensku, bola trať Košice-Kysak-Prešov, v dĺžke 33 km. Premávka na nej začala 1. 9. 1870. O rýchlosti, s akou stavba napredovala, svedčí fakt, že v Žiline ešte 24. júna 1870 bola dražba na vyťaté vŕby a topole na mestskej sihoti pri Váhu, kadiaľ mala viesť trať, a už o pol roka neskôr, 20. 12., šiel na úseku Tešín-Žilina prvý skúšobný vlak. Pravidelná premávka na tomto úseku začala 8. januára 1871.

Ďalším úsekom odovzdaným do prevádzky koncom toho istého roku bola trať z Popradu do Žiliny, v dĺžke asi 130 km. Prvý vlak z Popradu odišiel 7. 12. 1871 o 23:25 hod. a do Žiliny prišiel 8. 12. o 6:00 ráno. V decembri 1871 bol odovzdaný na premávku ešte úsek z Popradu do Spišskej Novej Vsi. Toto rýchle napredovanie stavby narušilo a dočasne zastavilo zosypanie skalnej úbočiny pri Krompachoch, a preto úsek trate zo Spišskej Novej Vsi do Kysaku bol otvorený ako posledný až 18. 3. 1872. To bol aj deň začatia premávky na celej trati z Košíc do Bohumína aj s prípojnou železnicou do Prešova.

Celá železnica bola postavená za necelé tri roky, s výnimkou krátkeho sliezskeho úseku, postaveného ešte v roku 1869. Aj keď bola trať stavaná ako jednokoľajná, bola to vzhľadom k dĺžke a obtiažnosti stavby, najmä v horskom teréne, úctyhodná rýchlosť. Akcionárov v tejto rýchlosti poháňal termín dokončenia stavby a odovzdania trate do prevádzky, určený koncesnou listinou na 26. 6. 1872, teda šesť rokov od jej vydania. Samozrejme, že táto rýchlosť šla na úkor kvality stavby. Hneď po otvorení premávky boli preto mnohé úseky opravované a tiež stavby staníc, hlavne vedľajších budov, neboli všetky používateľné.

Dátum uvedenia do prevádzky        Traťový úsek                              Dĺžka v km

1. 2. 1869                                Bohumín-Tešín                                     31

1. 9. 1870                                Košice – Kysak – Prešov                       33

8. 1. 1871                                Tešín – Žilina                                       69

8. 12. 1871                               Žilina – Poprad                                   138

12. 12. 1871                             Poprad – Spišská Nová Ves                 27

18. 3. 1872                              Spišská Nová Ves – Kysak                   68

Vybudovanie hlavnej trasy Košicko-bohumínskej železnice umožnilo stavbu viacerých prípojných miestnych železníc z oblastí inklinujúcich k oblasti hlavnej trasy. Boli to hlavne oblasť Spiša, Vysokých Tatier, Liptova, Oravy a Kysúc.

Kvôli zrýchleniu a zrentabilneniu Košicko-bohumínskej železnice boli už od začiatku snahy o jej zdvojkoľajnenie. Na začiatku 20. storočia a v jeho tridsiatych rokoch sa to však podarilo iba v niektorých úsekoch. Celá trať bola zdvojkoľajnená až v roku 1955 v rámci výstavby Trate družby. V roku 1964 bola dokončená elektrifikácia celého úseku trate.