Tilbage i 1844 opstod de første planer om en jernbane fra Hamburg i Tyskland til Aalborg.
Efter mange diskussioner frem og tilbage blev der den 10. marts 1861 vedtaget en lov om bygning af denne jernbanestrækning.
Banen blev bygget for statens regning af det engelske entreprenør Peto, Brassey & Betts, der var et kæmpeforetagende med titusindvis af ansatte i adskillige lande verden over. Strækningen Randers – Aalborg var sidste del af dette projekt som skulle være færdigt 1. september 1869.
Forarbejdet til denne strækning blev startet i oktober 1865 og det efterfølgende forår påbegyndtes arbejdet. Jordarbejdet blev udliciteret til underentreprenører, som ansatte daglejere til at udføre arbejdet. Daglønnen var almindeligvis en rigsdaler (to kroner), men når vejret standsede arbejdet, blev der ikke udbetalt løn. Arbejderne måtte selv sørge for kost, så mange landmænd fik en ekstraindtægt ved at holde marketenderi.
MZ på vej mod syd ved Ellidshøj i 80’erne. Sidesporet er i dag fjernet.
Jordarbejdet blev indledt med skovle og trillebøre, der blev skubbet ad udlagte planker. Når banelegemet var bredt nok, anlagde man et arbejdsspor med almindelig sporvidde, så jorden kunne køres bort i hestetrukne, flade vogne med en lasteevne på ca. 5 tons.
Den 19. september 1869 indvies banen med deltagelse af bl.a. kongeparret Christian IX og dronning Louise, samt den nygifte kronprins Frederik og hans søster prinsesse Thyra.
Den kongelige familie var om formiddagen kommet sejlende til Aalborg, og kl. 12.30 kørte indvielsestoget på ikke mindre end 17 vogne sydpå, her i blandt den såkaldte slesvigske kongevogn som ved samme lejlighed blev indviet efter en restaurering.
I toget var foruden kongefamilien i alt 236 indbudte gæster.
I Berlingske Tidendes referat 20. september 1869 af begivenheden hedder det:
“Kl. 12.35 afgik under hurraråb det af 17 waggoner bestående jernbanetog, i hvilket den bekendte smukke vogn, der tidligere har været benyttet på den slesvigske bane af Kong Frederik VII og nylig er blevet restaureret indvendig, benyttedes af den kongelige familie”.
Der er ingen tvivl om, at vognen skulle præsenteres ved denne lejlighed. Det hævdes i hvert fald, at den på vej fra Århus til Aalborg inden åbningshøjtideligheden var skjult af en presenning. Dette kunne dog også skyldes, at man ikke ønskede, at vognen skulle blive snavset på turen til Aalborg.
Dagen efter indledtes den ordinære trafik, hvor den første køreplan havde to persontog og et blandet dagligt i hver retning. Strækningen Aalborg – Randers tog ca. 2 timer 5 minutter – Diligencen var ca. 7-8 timer om turen – hvorfor postvæsenet nedlagde ruten.
Fra starten blev banen anlagt enkeltsporet, men under den 1. verdenskrigs voldsomme trafikbelastning var enkeltsporet utilstrækkeligt. Ved lov af 20. marts 1918 blev det derfor besluttet, at udvide banen til dobbeltspor.
Men det trak ud. – Først i slutningen af trediverne kom der, grundet den store arbejdsløshed, gang i arbejdet med anlægget af dobbeltsporet. Så sent som 6. maj 1953 blev dobbeltsporet mellem Støvring og Ellidshøj taget i brug og der var nu dobbeltspor hel til Aalborg.