Den 27 april 1898, beslöt den svenska riksdagen att godkänna avtalet för anläggande av järnväg mellan Malmberget och Victoriahavn/Narvik. Kort därefter sattes det omfattande ar­betet igång. Det tidigare konkur­sade engelska bolaget hade hunnit anlägga en provisorisk järn­vägssträckning för främst mate­rieltransporter till järnvägsbygget, en sträcka på drygt 20 km norr om Malmberget, vilken fanns kvar ända fram till omkring 1895, då staten beordrade att sträckan skulle rivas upp och av­vecklas.
 
Innan tillståndet för den nya koncessionen gavs, snabbutreddes även en alternativ östlig sträckning över Svappavaara malmfält, där de kända järn- och kopparmineraliseringarna främst i Mertainen och Svappavaara var föremål för exploateringsplaner av olika intresse­grupperingar. Just dessa fyndigheter hade Lundbohm inventerat och kartlagt redan sommaren 1890. Staten beslöt emellertid att det västra alternativet skulle genomföras eftersom sträckan var färdigprojekterad och det östra alternativet skulle både fördyra och fördröja hela projektet. När det slutgiltiga beslutet väl kom, hade arbetet redan startat i förtid eftersom man hade för­väntat sig detta beslut, och en ca 23 km lång bansträckning var redan lagd.
 
Det omfattande järnvägsbygget Malmberget –Victoriahavn var på svenska sidan av gränsen uppdelat i två olika huvuddistrikt, det södra respektive det norra distriktet. På den norska sidan var arbetssträckan indelad i två avdelningar, och här använde man sig i stort sett av det tidigare engelska bolagets The Northern Europe Railway Co. Ltd upplägg vad gäller etapper och stakning av banans sträckning. Det södra distriktet på den svenska sidan omfattade sträckan Malmberget – Torneträsk, ca 160 km, medan det norra distriktet avsåg distansen mellan Torneträsk och Riksgränsen, en sammanlagd sträcka på ca 77 km. Det södra distriktets längre sträck­ning berodde främst på de olika terrängförhållandena som förelåg. Medan det södra distriktet präglades av låglänt myrlandskap utgjorde det norra distriktet av ett svårforcerat landskap med omfattande schaktnings-, skärnings- och tunnelarbeten.
 
I arbetet med järnvägen användes, främst inom det södra distriktet, den amerikanska metoden för järnvägsbygge - loket först. Metoden innebar helt kort att större delen av arbetsstyrkan var samlad framför rälsläggningen där arbetet med att bygga upp och stärka banvallen successivt genomfördes. Denna metod var speciellt tillämpbar i det flacka landskapet som södra distriktet var präglat av. Metoden medförde att man byggde väldigt snabbt en provisorisk skenlagd bana, på vilken man kunde frakta materiel på ett effektivt sätt. Att järnvägens provisoriska skenläggningar gick så snabbt, underlättade betydligt även Lundbohms för­beredelser för gruvan och samhällsuppbyggandet.
 
Järnvägsbygget på den norska sidan av banan kom igång något senare eftersom
koncess­ionsansökan beviljades av den norska staten först i augusti 1898.  Här använ­des, som påpekats, i stort sett samma stakningslinje som den det engelska bolaget tidigare gjort. Skillnaden var att man inte lät genomföra bygget av en del broar, utan i stället valde att bygga tunnlar som ansågs ge en säkrare drift av banan, i synnerhet under vintertid.