Ďalším krokom k výstavbe železnice medzi Uhorskom a Haličou sa stal v roku 1868 definitívny výber jej trasy, ktorý si vynútila naliehavá urgencia ríšskeho ministerstva vojny, adresovaná obom vládam. Tie vykonali opätovný prieskum lupkowskej i dukelskej trasy a v protokole zo spoločnej porady zástupcov oboch vlád i ríšskeho ministerstva vojny dňa 3.11.1868 sa všetci zúčastnení vyslovili pre lupkowský variant (zo Somboru na Tiskej železnici cez Sátoraljaújhely, Veľaty, Trebišov, Michalovce, Humenné, Medzilaborce, Lupków, Lisko a Chyrów do Przemyslu), zodpovedajúci takmer úplne návrhu rakúskej trasovacej komisie z roku 1866 (o koncesiu na železnicu tejto trasy požiadal už 4.3.1868 Aladár Andrássy a Adam Potocky).
Uhorská vláda ešte v tom istom roku (29.11.1868) predložila legislatíve návrh zákona o koncesii uhorskej trate Michaľany – Lupków. Koncesia na ostatné uhorské železnice tejto trasy bola už v júli 1868 udelená konzorciu neskoršej spoločnosti Uhorskej severovýchodnej železnice. Osobná averzia niektorých poslancov uhorského parlamentu k žiadateľom o koncesiu síce spôsobila – okrem označenia projektu ironickým pomenovaním „rodinná železnica“ – určité prieťahy v koncesnom procese, napokon však bola koncesia po rokovaní v dňoch 12. a 13.7.1869 konzorciu, tvorenému grófmi AdamomPotockým, Aladárom Andrássym, kniežaťom Augustom Sulkowským, Vincentom Kirchmayerom, rytierom Žigmundom Kozlowským, Móricom Krainszkým, Leonardom Truskolowským, Jozefom Tyczkowszkým, Kolomanom Forgáchom, Antalom Sztáraym, barónom Jánom Frölichom, Filipom Harkányim, Jozefom Gräflom a Gabrielom Lónyayom, udelená a zákonným článkom č. VI v tom istom mesiaci aj sankcionovaná. Koncesia poskytovala podniku štátnu garanciu 40 000 zl na míľu železnice. To isté konzorcium obdržalo 11.9.1869 koncesiu i na haličské trate plánovanej železnice.
Podľa koncesie, udelenej uhorskou vládou, boli koncesionári povinní do dvoch rokov odo dňa účinnosti zákona, t.j. do 31.7.1871 realizovať úsek Michaľany – Humenné a úsek Humenné – zem. hranica v nadväznosti na termín začatia stavby úseku zem. hranica – Szczawne – Zagorz – Lisko – Chirów – Przemysl. Vyvlastnenie sa povolilo pre jednokoľajnú trať. V prípade prekoročenia ročného hrubého príjmu 120 000 zl rak. meny na 1 míľu sa rušila štátna garancia prokov a spoločnosť bola povinná zabezpečiť na vlastné náklady zdvojkoľajnenie trate. Koncesionári boli za účelom získania potrebných informácií oprávnení založiť akciovú spoločnosť, museli však do 14 dní odo dňa vydania koncesie zložiť v hotovosti 150 000 zl a do 3 mesiacov preukázať, že sa podarilo zabezpečiť 30% kapitálu.
Po udelení koncesie sa sprvu veci vyvíjali pomerne úspešne. Obstarávania finančných záležitostí sa ujal bankový ústav Creditanstalt, ktorému sa podarilo krátko po udelení koncesie zrealizovať na burze 62 000 akcií po 200 zl. Prvé signály neskorších komplikácií však prišli vzápätí – celý rad oslovených stavebných podnikov považoval za nemožné uskutočniť plánovanú výstavbu za vytvorený koncesný kapitál a až v marci sa podarilo uzatvoriť zmluvu o výstavbe železnice v „generálnom akorde“ s podnikateľstvom bratov Braunov (uhorský úsek) a grófom Karolom Mierom (haličský úsek). Výstavba vrcholového tunela pri Lupkówe nebola v týchto zmluvách zahrnutá; jeho stavby sa napokon ujali koncesionári sami v spoločenstve s oboma na stavbe zúčastnenými podnikateľstvami. Stavba uhorského úseku začala 12.3.1870. Štatút akciovej spoločnosti s názvom „Prvá uhorsko-haličská železnica“ bol schválený 19.11.1870, stavebný kapitál 31 500 000 zl reprezentovalo 62 500 akcií a 95 000 prioritných obligácií po 200 zl. Zhruba 40 000 prioritných obligácií sa podarilo Creditanstaltu realizovať v kurze 87% už 18.4.1871. Až do zriadenia akciovej spoločnosti dozeral na priebeh výstavby, riadenej stavebným riaditeľom Rudolfom Guneschom, užší výbor akcionárov.
Stavba železnice napredovala v rovinách medzi Michaľanmi a Humenným pomerne rýchlo, takže tento 64,6 km dlhý úsek bol odovzdaný prevádzke už 25.12.1871 (aj keď i tento termín odovzdania stavby znamenal trojmesačný sklz oproti plánu). Už vtedy však začínalo byť všetkým zúčastneným jasné, že ďalej to nebude vôbec jednoduché. Staviteľ gróf Mier sa rozhodol odstúpť od záväzku dostavať svoj úsek železnice na haličskej strane, čo sa mu aj podarilo, takže akcionári museli pokračovať v vstavbe vo vlastnej réžii. Situácia sa skomplikovala aj na uhorskom úseku – ukázalo sa totiž, že uhorskou koncesiou stanovené najvyššie stúpenie 14,3 – 16,6‰ sa na rampe v Medzilaborciach nedá dodržať. Po dočasnom upokojení situácie sa objavili vážne problémy pri výstavbe vrcholového tunela. Jeho stavbu zahájila stavebná spoločnosť bez náležitého geologického a terénneho prieskumu. Navyše sa čoskoro ukázalo, že použitá belgická tunelovacia metóda nie je pre konkrétny tunel príliš vhodná a najmä, že kvádre tunelovej obmurovky z karpatského pieskovca nemajú pre svoje použitie patričné fyzikálne vlastnosti. Veľmi vlhká jeseň a neskorý príchod mrazov spôsobili v roku 1872 zosuvy tunela i okolných svahov. Komisia odborníkov po obhliadke vzniknutej škody dospela k rozhodnutiu skrátiť tunel takmer na polovicu, upraviť tunelový prierez a zosilniť tunelový obmurovku granitovými kvádrami, dovážanými až z Čiech a Horného Rakúska. Prácu spomalila i epidémia cholery, pred ktorou mnohí roborníci zo stavby ušli.
Všetky tieto mimoriadne okolnosti významným spôsobom narušili hospodárenie spoločnosti. Do októbra v roku 1872 krátkodobá dlžoba spoločnosti narástla na 4,5 mil. zl, pričom tunel ešte nebol zďaleka dostavaný. Skutočné náklady jeho výstavby dosiahli napokon trojnásobnú hodnotu pôvodného rozpočtu. V roku 1872 preto kontrahovala správna rada spoločnosti so súhlasom generálneho zhromaždenia nezaložený dlh 2,3 mil. zl a obrátila sa na rakúsku i uhorskú vládu s cieľom dosiahnuť uhradenie vykonaných nadprác a zvýšiť štátnu garanciu na najvyššiu možnú mieru, povolenú koncesným zákonom. Posledný ústupok získala spoločnosť pomerne rýchlo, keďže obe vlády túto žiadosť predpokladali a už 21.12.1869 dosiahli pre predpokladané zvýšenie garancie, rovnocenné kapitálovému navýšeniu o 45 000 zl na míľu železnice, čo jej umožnilo vydať ďalšiu emisiu 1698 akcií a 1465 prioritných obligácií po 200 zl, t.j. v nominálnej hodnote 632 600 zl. Pokračujúce rokovania o ostaných žiadostiach spoločnosti však nepriaznivo zasiahol krach na viedenskej burze. Samotná výstavba napriek všetkým ťažkostiam medzitým pokračovala a do augusta 1872 bol dostavaný úsek z Humenného k pohraničnému tunelu. Je zaujímavé, že prevádzka na tomto úseku nezačala hneď po ukončení jeho výstavby. Dôvodom bola skutočnosť, že úroková záruka na trať mala vstúpiť do platnosti až po otvorení tunela. Problém odstránil napokon zákonný článok č. XXIII/1873. Z Medzilaboriec k lupkówskemu tunelu sa na jeho základe začalo jazdiť až 12.6.1873, pričom dopravu medzi haličskou a uhorskou časťou železnice zabezpečovala spoločnosť až do dostavby tunela vlastnou povozníckou službou.
Pri výstavbe trate, ktorá prechodovýcm prierezom zodpovedala štátnym železniciam, sa presunulo asi 2,0 mil. m3 zeminy. Na uhorskom úseku trate bolo 10 staníc a 3 zastávky, v ktorých sa vybudovalo 13 príjmacích budov, 15 skladísk a 9 nakladacích rámp. Na trati bolo 74 strážnych stanovíšť a 196 mostov. Dva najväčšie cez Ondavu a Laborec mali drevenú konštrukciu. Na trati boli tri výhrevne a jedna dielňa.
© ŽSR - Železničné telekomunikácie na základe publikácie: Dejiny železníc na území Slovenska. Vedúci autorského kolektívu Ing. Jiří Kubáček CSc.