Området har været beboet siden oldtiden. Sundby nævnes første gang i 1202, da kong Valdemar Sejr overdrog stedet til Vitskøl Kloster. Efter Reformationen i 1536 overgik Sundby til kronen, og byen havde privilegiet til færgefart over fjorden. Relationen til den større by Aalborg er en gennemgående faktor i Sundbys historie.
Under Trediveårskrigen anlagde kejserlige tropper 1627‑29 en stjerneskanse på Sundby Bjerg. I 1644 blev byen angrebet og besat af svenske tropper, hvilket skete igen i 1657. Kronen afhændede i 1667 Sundby Gods til stadshauptmand Frederik Thuresen. Siden skiftede byen hænder flere gange. I 1700-tallet udviklede en række håndværksvirksomheder sig til småindustri. En af de første, der fik privilegium, var et kridtpibemageri.
Fra midten af 1800-tallet begyndte Sundbys, fra 1825 Nørresundbys, vækst og en spæd industrialisering. I 1856 fik byen status af handelsplads, og den blev købstad i år 1900. Af industrivirksomheder kan nævnes maskinfabrikken Gabrielsværk (oprettet 1855), Andelssvineslagteriet (oprettet 1891) og A/S Svovlsyre og Superphosphat-Fabrik (oprettet 1913). Nørresundby Portland Cement Fabrik i Nørre Uttrup (oprettet 1908) og Dansk Andels Cementfabrik (DAC) i Lindholm (oprettet 1913) har også spillet en vigtig rolle i udviklingen.
Gennem 1900-tallet fortsatte byens vækst som følge af den fortsatte industrielle udvikling, og frem til midten af 1900-tallet spillede Nørresundby en selvstændig rolle som oplandsby med landbrugsorienteret service og industri, men efterhånden blev den inddraget i byen Aalborg. Dette indebar bl.a., at byens centerfunktioner i nogen grad blev overtaget af Aalborg. I 1968 blev Nørresundby sammensluttet med Sundby-Hvorup og Egholm i et fejlslagent forsøg på at danne en storkommune nord for Limfjorden. Nørresundby blev en del af den nye Aalborg Kommune i 1970.
Befolkningstallet kulminerede i 1960’erne med ca. 23.000 indbyggere, hvorefter en markant deindustrialisering satte ind, og Nørresundby blev boligforstad til Aalborg.
