Použití kolejí k usnadnění dopravy a snížení nákladů především v dolech je známo už z doby husitské, tedy z 15. století. Později se jízda do kopce usnadňovala parním strojem stojícím na kopci, který vytahoval vagonky nahoru. První jízda skutečné lokomotivy se konala 21. února 1804 a jejím autorem byl otec parního vozu Richard Threvithick. Na první jízdě uvezla 10 t litiny a pět vozů s šedesáti lidmi, urazila asi 15 km za čtyři hodiny, spotřebovala 200 kg uhlí. Je zajímavé, že proti dalšímu vývoj parních lokomotiv bojoval James Watt. Trevithick pracoval na dalším stroji i na zdokonalení kolejnic. Ale vydal se ze všech peněz a skončil ve vězení pro dlužníky.
Stejně jako v historii parního vozu, i v dalším vývoji parních lokomotiv se objevilo několik kuriózních myšlenek. Pokračovatelem Richarda Threvithicka se stal George Stephenson a jeho syn Robert. George Stephenson se vypracoval od pouhého topiče u parního stroje v dolech až po vedoucího, jehož prvním úkolem bylo snížit náklady za dopravu uhlí od dolu do přístaviště. Začal se proto zajímat o lokomotivy. Žádná ze současných konstrukcí ho neuspokojovala, proto se počátkem roku 1813 rozhodl, že postaví ve vlastní dílničce lokomotivu podle svých plánů. Byla hotová v polovině roku 1814, 25. července podnikl první zkoušku. Lokomotiva uvezla osm vozů o hmotnosti 30 t, jela rychlostí asi 7 km/h do kopce se stoupání 1:450. V roce 1815 si nechal svoji lokomotivu patentovat a o rok později ošetřil patentem i její zlepšení. Mezi jinými spřáhl kola tendru s hnacími koly parovozu – zvýšilo se tření mezi koly a kolejnicemi a stroj utáhl větší náklad – zavedl parní tlumiče nárazů (parní polštáře) a zlepšil litinové kolejnice, vyztužil je parabolickým žebrem. Stephenson pak pracoval na stavbě železničních drah a zřídil první továrnu na lokomotivy.
První železnicí na evropském kontinentu byla koňská dráha z Budějovic do Lince dlouhá 131 km. Stavěl ji František Gerstner a již tehdy ji projektoval tak, aby po ní mohly jezdit parní lokomotivy. První parní železnice v Rakousku byla zřízena v roce 1838 z Vídně do Wieliczky. První trať v Čechách, z Třebové do Prahy, byla otevřena roku 1845. Trať z Pardubic do Prahy projektoval Jan Perner.