Het eerste begin
De gouverneur-generaal van Nederlands-Indië, de heer Sloet van de Beele, legde op 17 juni 1864 de eerste steen voor het station Kemijen (nu gelegen in het oosten van de stad Semarang). De NV Nederlandsch Indische Spoorweg Maatschappij (NIS) begon op dat moment 26 kilometer lange spoorweg van Kemijen naar Tanggung, net ten oosten van Semarang. In 1867 werd deze eerste lijn geopend, en in 1870 was de spoorweg al verlengd tot 110 kilometer, waardoor van Semarang naar Solo gereisd kon worden.
De NIS leed grote verliezen en had overheidssteun nodig voor het voltooien van de eerste lijn, tot aan Jogjakarta. Inmiddels was berekend dat het goedkoper zou zijn om spoorlijnen niet met normaalspoor (143,5 cm breed) aan te leggen, maar met een smaller spoor van 106,7 centimeter. Het werd toen vastgelegd in de wet dat spoorwegen alleen in die spoorwijdte aangelegd mochten worden.
De eerste spoorlijn met het smallere spoor werd door de NIS aangelegd tussen Batavia (nu Jakarta) en Buitenzorg (nu Bogor). De aanleg van spoorwegen op Java ging vervolgens erg snel en in 1888 waren er twee losstaande netwerken ontstaan. Het netwerk van Centraal- en Oost-Java verbond onder andere de steden Semarang, Solo, Jogjakarta, Surabaya en Malang. Het netwerk van westelijk Java verbond Batavia met Buitenzorg, Sukabumi, Bandoeng (nu Bandung), Bekasi en Tandjoeng Priok (nu Tanjung Priok, de haven van Jakarta). Daarnaast was er nog een kort lijntje bij Tegal in Centraal-Java, niet verbonden met de andere lijnen.
Niet alle bovenstaande lijnen waren gebouwd door de NIS. De liberale Nederlandse regering wilde eigenlijk dat private bedrijven de spoorwegen aan zouden leggen, maar door de financiële problemen bij de NIS en het strategisch belang van spoorwegen besloot de overheid zelf ook spoorlijnen te gaan bouwen. Onder de noemer Staatsspoor- en Tramwegen Nederlandsch-Indië (SS) werden vanaf 1876 spoorlijnen aangelegd.
In 1894 was de gehele verbinding tussen Batavia (Jakarta) en Soerabaja (Surabaya) gereed. De reistijd voor dit traject was toen 32,5 uur om de afstand te overbruggen. Omdat er ’s nachts rustpauzes waren, en er op twee plekken overgestapt moest worden vanwege verschillende spoorwijdtes, duurde de reis in totaal drie dagen. Toch was het een grote verbetering, want voorheen duurde de reis twee weken, per paard en wagen. Door de aanleg van verschillende nieuwe spoorlijnen en de opheffing van de nachtelijke rustperiodes werd de route tussen Jakarta en Surabaya steeds sneller. Tegen het einde van de koloniale tijd, in 1939, duurde de trip nog maar 11 uur en 27 minuten. Nu, in 2012, gaat de trein nog nauwelijks sneller, en duurt de reis 10 uur.
Spoorlijnen op Sumatra
De SS begon ook met de aanleg van spoorlijnen op Sumatra. In West-Sumatra en Atjeh werden lijnen aangelegd en de Deli Spoorweg Maatschappij (DSM) kreeg de concessie voor de aanleg van een spoorlijn in Noord-Sumatra.
De spoorlijn in Atjeh was de eerste lijn op Sumatra, in 1876 in eerste instantie vier kilometer lang. De spoorlijn was vooral voor militaire doeleinden gebouwd, voor de Atjeh-oorlog. Vanwege de voortdurende oorlog was er steeds verdere uitbreiding van de spoorlijn nodig, tot meer dan vijfhonderd kilometer. Uiteindelijk is de spoorlijn van militair belang geweest tot in de onafhankelijkheidsoorlog!
In West-Sumatra werd aan het einde van de negentiende eeuw ook een spoorlijn aangelegd. De spoorlijn, die onder andere Bukittinggi aandeed, was een bijzondere omdat er een 43-kilometer lange tandradbaan bij zat om een hoogteverschil van ruim 750 meter te overbruggen.
Buiten de eilanden Sumatra en Java (inclusief Madura) is er maar één openbare spoorweg gebouwd. Tussen 1922 en 1930 was er een 47 kilometer lange spoorlijn actief in Zuid-Sulawesi (toen Celebes geheten). Vanwege lage passagiersaantallen werd de lijn al snel gesloten. Op andere eilanden, zoals Kalimantan en Papoea, zijn alleen spoorlijnen aangelegd ten behoeve van mijnen of bosbouw.