I 2010 startede Bethaniakirken en børneklub på Gl. Lindholm skole i Nørresundby. David Højgaard (daværende præst i Bethaniakirken, Aalborg) fik sommeren 2011 i forbindelse med et arrangement med børneklubben, idéen om at starte en moderne kirke i Nørresundby. Han flyttede med sin familie i slutningen af 2015 til Nørresundby og d. 1. april 2016 startede han som præst og kirkeiværksætter i bydelen.
I sommeren 2016 blev der holdt forskellige sociale arrangementer i Lindholm Strandpark. I efteråret 2016 startede en månedlig samling op for børn, studerende og voksne. I 2017 er der desuden blevet afholdt MyLife Workshop i kulturhuset - kulturbroen www.kulturbroen.dk/
I november 2017 blev første gudstjeneste holdt og det næste år forsatte med en gudstjeneste per måned. I 2018 udviklede Nordstjernen sig med flere med nye tilbud: Kids Fun Night (event for børn/børnefamilier). Minigrupper for kvinder eller mænd. Nordstjernen Outdoor (kulturelle og sociale arrangementer). I 2019 er flere ting yderligere blomstret frem: krea-hygge for kvinder, foredrag, Elsk Nørresundby (koncept om at gøre noget godt for ens bydel og engagere folk i venlighed, hjælpsomhed og gæstfrihed) og netværksgrupper.
