Spotreba uhlia v Uhorsku na začiatku 60. rokov rástla. V máji 1861 sa preto ustanovila Kameňouhoľná banská spoločnosť sv. Štefana, usilujúca sa využiť uhoľné zásoby salgótarjánskeho revíru. Generálne zhromaždenie tejto spoločnosti dňa 29.9.1861 prijalo rozhodnutie postaviť železnicu Lučenec – Fiľakovo – Salgótarján – Pásztó – Hatvan – Aszód – Isaszeg – Pešť a pre tento účel vymenovalo výbor, ktorý požiadal ešte v tom istom roku miestodržiteľskú radu o udelenie koncesie na plánovanú železnicu, pričom vo svojej žiadosti poukázal na možnosť dosiahnuť jej výstavbou ovládnutie peštianskeho uhoľného trhu a zvýšenie ťažby dvoj až trojnásobne. V žiadosti tiež spomenul možnosť pokračovať vo výstavbe železnice ďalej ku stredoslovenským banským mestám.

Miestodržiteľská rada, uhorská dvorská kancelária a napokon 6.5.1862 aj ríšske ministerstvá vojny a obchodu doporučili predloženej žiadosti vyhovieť a vyzvali súčasne spoločnosť urýchlene realizovať potrebné prípravné práce. Napokon bola spoločnosti udelená 19.1.1863 na 90 rokov koncesia, ktorá zaväzovala združenie postaviť do roku 1866 železnicu Pešť – Lučenec a do roku 1870 železnicu Lučenec – Banská Bystrica. Spoločnosť zmenila názov na C. k. súkromná Peštiansko-lučenecko-banskobystrická železničná a svätoštefanská kameňouhoľná banská spoločnosť a účastinný kapitál bol stanovený na 18 miliónov zl, pričom polovica mala byť tvorená účastinami po 200 zl a zvyšok dlhopismi.

Účastiny sa nedarilo predávať tak, ako si zástupcovia spoločnosti predstavovali. V tomto období však nastala bieda a hlad v oblasti plánovanej výstavby železnice rozmer regionálnej pohromy. Uhorský dvorský kancelár odoslal 24.6.1863 na ministerstvo financií nótu, ktorá navrhovala opatrenia na riešenie katastrofálnej sociálnej situácie a usiloval sa svojimi návrhmi usmerniť vládnu pozornosť na pomoc práve spoločnosti Peštiansko-lučenecko-banskobystrickej železnice. Podstatou návrhov bolo udelenie štátnej úrokovej záruky prioritných obligácií, čo by spoločnosti umožnilo získať podporu viacerých bankových úradov. Výnosom zo dňa 18.8.1863 prisľúbilo ministerstvo financií prevziať štátnu záruku polovice prioritnej pôžičky spoločnosti v objeme 4,5 mil. zl. Tento prísľub však viazalo na uskutočnenie ustanovujúceho zhromaždenia účastinárov spoločnosti o predloženie stanov na schválenie. Keďže by to znamenalo značné zdržanie, vystúpila spoločnosť so žiadosťou o pôžičku 1 mil. zl poskytnutej z rezervného fondu Uhorského kráľovstva, ktorú však minister financií viazal zas na súhlas ríšskej rady. Železničná spoločnosť sa preto rozhodla nestrácať ďalej čas a na generálnom zhromaždení dňa 15.9.1863 ohlásil jej riaditeľ Jozef Havas začiatok prác na úseku Hatvan – Salgótarján vlastnými prostriedkami. Udalosti dostali pomerne rýchly spád. Po začatí prác sa nezamestnaní záujemci hlásili v takom počte, že disponibilné prostriedky boli za necelý mesiac vyčerpané. Dvorský kancelár vo svojej kompetencii udelil uhorskej miestodržiteľskej rade 4.11.1863 telegraficky pokyn vyplatiť spoločnosti preddavok zo zemského fondu, keďže zo zastavenia prác hrozili nepokoje. Dodatočný cisársky súhlas bol udelený 19.11.1863. V novembri a decembri 1863 bolo potom spoločnosti v týždenných splátkach po 6 000 zl vyplatených 24 000 zl a prisľúbených ďalších 400 000 zl.

Štatút spoločnosti bol prijatý 15.9.1863 na jej ustanovujúcom zhromaždení a schválený cisárom 23.3.1864 sa však čoskoro ukázal ako nie príliš vhodný pre zaobstaranie potrebného kapitálu. Keď bolo spoločnosti cisárskym rozhodnutím povolené začať s jeho upisovaním, stanovili si viedenské bankové ústavy podmienku preložiť sídlo spoločnosti do Viedne a podriadiť ju rakúskemu obchodnému právu. To si zas vyžiadalo upraviť štatút spoločnosti. Upravený štatút potom získal cisársky súhlas 28.11.1864 a stanovoval nakladací kapitál spoločnosti na 12 mil. zl, z toho 6,6 mil. zl v účastinách a 5,4 mil. zl v strieborných prioritných obligáciách. Nepomohlo to však a plánované finančné operácie sa nepodarilo plne zrealizovať. Napokon 11.7.1865 bol na celý podnik vyhlásený konkurz. Bol to prvý konkurz železničnej spoločnosti v monarchii, pričom jej stavba ešte stále nedosiahla slovenské územie.

Pre Uhorsko mala však plánovaná železnica veľký význam. Kráľovská uhorská komora preto bojovala ďalej a 5.7.1866 zaslala cisárovi memorandum, kde žiadala pokračovať v ďalšej výstavbe. Na základe tohto memoranda schválil cisár 7.9.1866 dohodu o sanácii medzi štátnou správou a železničnou spoločnosťou, podľa ktorej bolo zo štátneho pokladu uvoľnených 1,8 mil. zl za zabezpečenie výstavby, 200 000 zl na krytie prvých kupónov vydaných prioritných obligácií, 800 000 zl na pokrytie požiadaviek za skôr dodaný železničný materiál a 400 000 zl na pokrytie pôžičky z roku 1863 pre uhorský zemský fond. Ďalej dohoda obsahovala záväzok štátu poskytnúť ďalších 1 mil. zl. Spoločnosť sa zaviazala stiahnuť staré prioritné obligácie, ktoré boli nahradené novou pôžičkou v rovnakej výške a použiť fond, vytvorený štátnou podporou výlučne na dostavbu železnice a jej sprevádzkovanie. Pre jeho kontrolu bol vymenený vládny komisár Karol Huszár s technickým asistentom. Na obdobie do vyrovnania novej prioritnej pôžičky vymenovala štátna správa do správneho orgánu spoločnosti dvoch správnych radcov. Veritelia spoločnosti vyjadrili s touto dohodou súhlas a konkurz mohol byť teda 6.10.1866 zrušený. Generálne zhromaždenie spoločnosti dňa 3.11.1866 prijalo rozhodnutie zmeniť názov spoločnosti na „C. k. privátnu Uhorskú severnú železnicu“.