Da Hvorup kirke har været sognets kirke i fl. 100 år, men sognet gik langt mod syd, tæt mod Nørresundby, og i midten af det 20 århundrede blev Nørre Uttrup stærkt udbygget og de fleste af sognets beboere boede her, kom de første tanker om at bygge en kirke i dette område. Man havde allerede 1936 bygget et Menighedshus lige nord for skolen.

Menighedshuset blev indviet i 1958 til kirkelige handlinger. Tanken om at bygge en ”rigtig” kirke opstod samtidig med. I 1963 blev der dannet en kirkekomite, som gik i gang med at fuldføre tankerne. Man fik arkitekt Johs. Exner til at tegne kirken, og byggeriet startede i 1975, og den blev indviet den 11. april 1977. Den er en moderne kirke, der foruden kirke, hvor der er godt 200 siddepladser, har menighedssal, der kan tilsluttes kirken. Der findes desuden konfirmandstue mindre lokaler og kontorer. Kirken blev udbygget i år 2000 med endnu en mødesal, en afd. med kirkekontor og øvrige kontorer til de ved kirken ansatte. Ved siden af kirken ligger præstegården, der blev bygget i 1974, tegnet af arkt, Exner.