De eerste spoorweg die de HSM aanlegde was de lijn van Amsterdam naar Haarlem, die op 20 september 1839 voor het publiek werd opengesteld. Hij bereikte Leiden in 1842, Den Haag in 1843 en Delft en Rotterdam in 1847. Deze lijn wordt ook wel de Oude Lijn genoemd. De aanleg van het traject tussen Den Haag en Rotterdam ondervond vertraging door een geschil met een grondeigenaar, beschreven in Het Laantje van Van der Gaag.

Deze eerste spoorlijn werd aangelegd met een spoorwijdte van 1945 mm. Alle latere spoorlijnen werden aangelegd met het inmiddels gebruikelijke normaalspoor (1435 mm). In 1866 was al het breedspoor omgebouwd tot normaalspoor.

Van het originele breedspoormaterieel is niets bewaard gebleven. Vanwege het 100-jarig jubileum in 1939, werd in 1938 van één van de eerste Nederlandse stoomlocomotieven De Arend met drie bijpassende personenwagons een replica gemaakt. Later kwam deze als statisch monument in het Nederlands Spoorwegmuseum te Utrecht. Bij de viering van het 150-jarig jubileum in 1989, werd de loc weer rijvaardig gemaakt. Bij speciale gelegenheden werd de locomotief weer onder stoom gebracht om op het terrein van het Spoorwegmuseum ritjes te maken. Hiervoor ligt een stuk breedspoor op het museumterrein. Sinds 2005 is deze trein onderdeel van de presentatie "De Grote Ontdekking" in het museum.

Het eerste station dat Amsterdam bediende was d'Eenhonderd Roe en lag ongeveer ter hoogte van de huidige Van Hallstraa. Destijds was dit nog grondgebied van de buurgemeente Sloten.

In 1842 kwam er een station bij de Willemspoort, de huidige Haarlemmerpoort, aan de westkant van de stad. Achter de poort lag een brug over de Singelgracht en daarachter lag het station, dus op de plek waar nu het Westerpark ligt. Verderop, richting centrum, aan de Haarlemmerhouttuinen bij het Singel, verrees in 1884 het hoofdkantoor van de maatschappij, gebouw Droogbak, ontworpen door Christiaan Posthumus Meyjes sr.. Van 1878 tot 1889 was het Station Droogbak vertrekpunt voor de treinen van de HIJSM naar Haarlem en Zaandam, tot de opening op 15 oktober 1889 van het Centraal Station.

Het eerste station van Haarlem (het huidige is het vierde) lag op de plek waar nu de Hoofdwerkplaats Haarlem ligt. In Leiden, Den Haag, Delft en Schiedam kwamen de stations te liggen op de nu nog in gebruik zijnde locaties. In Rotterdam eindigde de lijn tot 1877 bij de Delftsche Poort (station Delftsche Poort, daarna lag het aan het huidige Stationsplein. Het werd in 1957 vervangen door het Centraal Station).