W roku 1872 oddano do użytku normalnotorową linię Przemyśl – Łupków, należącą do Pierwszej Węgiersko-Galicyjskiej Kolei (EUGE). W ten sposób kolej dotarła w rejon Bieszczadów. Myślano o dalszej rozbudowie linii w kierunku Cisnej, jednak z uwagi na trudny profil linii i związane z tym koszty budowy oraz niewielkie zaludnienie regionu, projekt ten nie wszedł nigdy w życie. W 1890 r. w oparciu o ustawę krajową sejmu galicyjskiego z 25.08.1893 r. popierającą rozwój kolei lokalnych powstała „Spółka Akcyjna Budowy i Eksploatacji Kolei Lokalnej Nowy Łupków – Cisna”.
W 1890 r. rozpoczęto budowę liczącej 24,174 km długości linii , której otwarcia dokonano 22.01.1898 r. Początkowo kolej eksploatowała dwa, a później trzy parowozy produkcji firmy Krauss. Tabor wagonowy składał się z 2 wagonów osobowych, 2 bagażowych, 4 krytych i 46 towarowych odkrytych i był wyprodukowany w pobliskim Sanoku.
Codziennie wyprawiano jeden pociąg mieszany (towarowo osobowy) odjeżdżający z Cisnej o godz. 9:01 a wracający z Nowego Łupkowa o godzinie 16:37. Całą trasę pociąg ten pokonywał w blisko 3 godziny. W latach 1900 – 1904 wybudowano liczącą 20 km linię Cisna – Beskid. Linia ta łączyła się z istniejącą już koleją, lecz była odrębnym przedsiębiorstwem posiadającym 2 parowozy i 60 wagonów kłonicowych. Wywożono nią drewno z położonych na niej ładowni do Nowego Łupkowa.
Pomimo wybuchu w 1914 r. I wojny światowej ruch na linii Nowy Łupków – Cisna prowadzono nadal. Kursowały wówczas dwie pary pociągów. Jesienią 1914 r. nastąpił odwrót wojsk austro-węgierskich z terenu Bieszczad, co pociągnęło za sobą zamknięcie ruchu na kolei. Wkraczające wojska rosyjskie z uwagi na zły stan lokalnych dróg były bardzo zainteresowane wznowieniem ruchu na kolei dla potrzeb wojskowych. Dlatego też w kwietniu 1915 r. uruchomiono linię Nowy Łupków – Cisna.
W czerwcu 1915 r. po odwrocie wojsk rosyjskich wkraczające wojska austriackie ponownie uruchomiły linię Nowy Łupków – Cisna, która do końca wojny w 1918 r. służyła wyłącznie przewozom wojskowym. Ponieważ Rosjanie wywieźli dwa spośród trzech parowozów, austriackie wojska kolejowe sprowadziły czteroosiowy parowóz produkcji węgierskiej.