Vendsysselbanen blev indviet den 15. august 1871. Banen udgik fra Nørresundby (nuværende 'Lindholm station
' tilhørende DSB) til Frederikshavn. Senere kom der forbindelse til Aalborg via Jernbanebroen over Limfjorden, som blev åbnet for trafik 8. januar 1879.
Frederikshavn station blev flyttet i 1979 til den nuværende placering.
Strækningen betjentes udelukkende af DSB
før en sammenslutning i juni 2008, hvor Nordjyske Jernbaner fik lov til at køre på strækningen 1-2 gange i døgnet.