The railway began as the Palmerston and Pine Creek Railway, built when the Northern Territory was still administered by the Government of South Australia. A £959,300 contract was awarded to C. & E. Millar of Melbourne. Singhalese and Indian gangs did the heavy earthwork and grubbing; 3,000 Chinese labourers laid more than a kilometre of track per day. More than 300 bridges and flood openings were built to carry the narrow-gauge line through country that flooded each wet season with serious intent. The line reached Pine Creek in 1888 and officially opened on September 30, 1889 — the northernmost outpost of the South Australian Railways, in one of the most remote places the colonial government had yet claimed. When Federation transferred ownership to the Commonwealth in 1911, the federal government promised to extend the line south to Adelaide without specifying when. That 'when' would stretch for nearly a century.

The leisurely pace that defined Leaping Lena in peacetime vanished in 1942. When the Pacific War reached Australia's north — Darwin was bombed for the first time in February 1942 — the North Australia Railway became a critical strategic corridor. At peak operations in 1944, as many as 147 trains ran per week on a line built for far lighter traffic. The Commonwealth Railways improvised where it could: locomotive depots were expanded, workshops enlarged, water supply for steam engines increased. When troops needed to move north and there was nothing suitable to carry them, the railways simply converted cattle cars. The open-planked sides were lined, toilets installed, and men were loaded aboard. They headed north toward a theatre of war on a repurposed cattle train, on a narrow-gauge track through the bush, on a line that had always been about the making-do with what was available.

The post-war years did not redeem the railway's strategic importance. Extensions to the south were proposed — a line to Bourke in 1932, a connection to Dajarra in 1952 — and each time the federal Cabinet declined to proceed. The line subsisted on what traffic the Top End could generate. In May 1976, the federal government ordered closure, primarily due to the loss of iron ore traffic from the Frances Creek mine. Services ceased on June 30. Maintenance gangs withdrew in December 1977. Then, in 1978, heavy floods destroyed sections of track, removing any practical prospect of reopening. By 1985, the rails and steel sleepers were being lifted and shipped to Tasmania. Where the line had run, the bush quietly reclaimed what it had been given.

The dream of connecting Darwin to Adelaide by rail outlasted the North Australia Railway by more than two decades. In July 2001, construction began on a standard-gauge replacement: the Adelaide–Darwin railway line, built by a consortium with extraordinary speed — completed in roughly 26 months from start to finish. The new line broadly followed the old narrow-gauge route through parts of the Top End, but some 70 per cent of its alignment was entirely new. The Fergusson River bridge was the only piece of the original infrastructure retained. In January 2004, the first freight train from Adelaide reached Darwin. In February 2004, the first passenger service — The Ghan — completed the 2,979 km journey from Adelaide to Darwin, fulfilling the 121-year-old promise that Leaping Lena could only gesture at from its narrow tracks.