De første planer om en jernbane gennem Vendsyssel blev fremlagt i 1852, men først d. 24. april 1868 blev loven om et baneanlæg fra Nørresundby via Hjørring til Frederikshavn vedtaget. Bag anlæggelsen stod et konsortium under ledelse af baron G.A. Gedalia. Landskabet fordrede ikke større anlægsarbejder bortset fra nogle jordarbejder ved Tolne. Sandflugten skabte dog en del problemer og betød ofte ekstra gravearbejde. Banen blev indviet d. 15. august 1871 under overværelse af Christian 9. Det var første gang, at et dansk firma anlagde en jernbane herhjemme, hvilket vakte stor national begejstring. Anlægget gav konsortiet et pænt økonomisk overskud.
Der blev anlagt såvel stationer som trinbrætter på den 84,5 km lange, enkeltsporede jernbane. Nørresundby Station udgjordes af en genbrugt træbygning fra Fredericia Banegård, mens der blev opført værksted, remise m.m. i Frederikshavn. Her blev der senere også anlagt en havnebane. I den nuværende Brønderslev Kommune blev Vester Brønderslev Station det eneste stop på banen.
Der var etableret pontonbro over Limfjorden mellem Aalborg og Nørresundby i 1865, men kun for fodgængere og hestekøretøjer. Jernbanen indsatte derfor dampbåden S/S Lille Belt for at sejle passagerer og gods over fjorden, og der blev anlagt spor direkte ned til anløbsstederne.
Den 8. januar 1879 blev den første jernbanebro over Limfjorden åbnet, hvormed Vendsysselbanen fik forbindelse med jernbanerne i resten af Jylland. Broen var dengang et af de største og dyreste byggeprojekter i Danmark.