Door de vlucht, welke de tabakscultuur in Deli nam en in verband met de slechte toestand van de wegen, kwam J. Th.
Cremer, hoofdadministrateur van de Deli Maatschappij tot de overtuiging, dat het land rijp was voor een spoorweg. De plannen vonden in Nederland een goed onthaal en er werd concessie gevraagd door de Deli Maatschappij voor een spoorweg van Belawan via Medan naar Delitoewa met een zijtak van Medan naar Timbang Langkat (thans Bindjei geheten). Deze concessie werd bij besluit van de G.-G. van Nederlands-Indië d.d. 23 Jan. 1883 no. 17 verleend aan de Deli Maatschappij, die, van mening zijnde, dat het minder op haar weg lag zich met de exploitatie van de spoorweg te belasten, haar medewerking verleende tot de oprichting van de N.V. Deli Spoorweg Maatschappij, aan welke zij de concessie overdroeg.
Bij acte van 18 Juni 1883 werd de N.V. Deli Spoorweg Maatschappij opgericht. De concessie werd verleend voor 90 jaren, aanvankelijk gerekend van 1883 af, doch bij latere wijziging van 1 Jan. 1912 af. De spoorwijdte is 1,067 m- Het eerste baanvak van Laboean naar Medan werd op 25 Juli 1886 voor het algemeen verkeer opengesteld.
Nadien werden in het tabaksland herhaaldelijk nieuwe lijnen in exploitatie genomen tot in 1907 het net een lengte had van 250 km. Toen men zich ter Oostkust van Sumatra op de overjarige cultures wierp, heeft de N.V. Deli Spoorweg Maatschappij de ontginningen steeds op de voet gevolgd en in 1937 had het net een lengte van 553 km. Het uitgegeven aandelenkapitaal bedraagt ƒ18750000, terwijl aan onderhandse- en obligatieleningen een bedrag uitstaat van rond ƒ17000000.Vóór de Japanse bezetting waren de volgende lijnen in exploitatie, van Noord naar Zuid, van Besitang over Pangkalan Berandan, Medan, Tebing Tinggi, Kisaran naar Rantau Prapat. De zijlijnen lopen van Bindjei naar Kwala, van Medan naar Arnhemia en Batoe, van Loeboeq Pakam naar Bangoen Poerba, van Tebing Tinggi naar Siantar en van Kisaran via Tandjong Balei naar Telok Niboeng. In 1949 waren alle lijnen weder in het bezit van de Maatschappij, behalve het baanvak van Besitang tot Tandjong Poera. Gedurende de Japanse bezetting en daarna toen het bedrijf in handen van de Republiek was, heeft uit de aard der zaak een grote verwaarlozing plaats gevonden, maar in 1949 was zoveel gerehabiliteerd, dat het bedrijf aan alle aanvragen voor vervoer kon voldoen.
