Den gamle kirke ligger på kirkegården og er opført i den store kirkebygningsperiode i 1100-tallet. Man mener, at de mange kirker opførtes, fordi præsterne fik dåbsret. Denne havde hidtil været forbeholdt biskopperne. Men nu kom dåben ud til sognekirkerne.
Kirken har gennemgået en del forandringer gennem tiderne og er blevet restaureret flere gange. Men den blev opført i romansk stil, dvs. Roms kirker og paladser var forbillede. Den har et skib, et kor og en apsis (den rundbuede tilbygning mod øst), som inde i kirken har et halvkuppel hvælv. Koret er smallere end skibet, og grænsen mellem dem består af en mur – triumfvæggen – som gennembrydes af korbuen.
Ydermuren er lavet af store, tilhuggede firkantede granitsten – kvadre. Den indvendige mur er lavet af grovt tilhuggede sten, som er kalket. Muren er over 1 meter tyk. I koret er der på sydsiden et hul, som kunne være et ”spedalskhedshul”, dvs. et hul, hvorigennem spedalske kunne følge gudstjenesten og modtage nadveren. Men det er det ikke, siger man fra Nationalmuseets side. Det må være en ventilationskanal. Dette gælder også det andet hul i vestmuren ved klokkestablen. I dag er der sået tvivl om disse huller. Der er måske tale om vinduer til skriftemål.
Der er 3 romanske vinduer i kirken. De er rundbuede og forholdsvis små og er placeret højt. Der er et på nordsiden af koret, et i apsis og et tilmuret på nordsiden af skibet.
Den romanske kirke er ligesom sluttet om sig selv med de meget solide mure og højtsiddende vinduer. Og i modsætning til mange andre kirker i landet har de vendsysselske kirker tilsyneladende ikke nogen særlig rig udsmykning. Måske fordi der her i landsdelen er tradition for at udtrykke sig enkelt. Men man kan ikke med sikkerhed afgøre, om der har været kalkmalerier i denne kirke.
Der var som regel 2 indgange i de romanske kirker – 1 på sydsiden til mændene og 1 på nordsiden til kvinderne. Dette gjaldt også kirken i Brønderslev. Den nordlige dør er i dag tilmuret. Ved klokkestablen sidder der en granitkvader med et trappeformet hul. Kvadren mener man stammer fra alterbordet og har været et relikviegemme. Relikvier havde stor betydning i den katolske kirke, som jo var eneste kristne trosretning herhjemme indtil omkring 1520-30erne. De største kirker gjorde krav på at være bygget over den grav, hvor den helgen, som kirken var indviet til, lå begravet. De mindre kirker måtte nøjes med relikvier fra deres helgener. Det kunne være en benstump, en tøjstump eller lignende.
Det fremgår ikke, hvilken helgen kirken i Brønderslev var indviet til.
Døbefonten er også romansk. Den er hugget af sten til pokalform. Man ved, at børnene blev dyppet helt ned under vandet ved dåben. Vandet var indviet og blev kun udskiftet få gange om året. Der kunne godt være frostgrader i de uopvarmede kirker. Efterhånden gik man over til at sætte dåbsfade i døbefonten. Det gamle dåbsfad er overflyttet til den nye kirke, og et nyt er kommet i stedet.
I den romanske periode, dvs. frem til omkring 1250, var kirken forbeholdt stormændene, der var frie jordbesiddere. De var bygherrer og brugere af kirken. Næsten alle småbønder var dengang fæstebønder på de store ejendomme som f.eks. Kornumgård, Nibstrup, Hjermitslevgård. Siddepladserne i kirken var fastmurede bænke langs væggen , og der var plads til ca. 50 personer. Kirken har haft fladt træloft og mindst ét alter – hovedalteret – placeret i midten af apsis.
Den gotiske del af kirken. Perioden fra ca. 1250 – ca. 1500. Denne periode er kendetegnet ved, at det meste byggeri er om- og tilbygninger. Men der kommer mere lys ind i kirkerne i denne tid. De eksisterende vinduer gøres ofte større, og nye vinduer isættes. Kirkerummet bliver højere og større. Der bygges tårn, våbenhus. Døbefonten flyttes fra midten af kirken op i koret. Der kommer bænke på gulvet. Det vigtigste af alt er dog, at nu var kirken for alle.
I Brønderslev blev træloftet erstattet af nye stjernehvælv, og der blev opført et våbenhus, og indgang og vinduer blev større. Koret blev adskilt fra apsis på et tidspunkt mellem år1400 og 1600.
Kirken fik et tårn, måske med spir. Tårnets nederste del udgjorde en forlængelse af skibet. I tårnet har der hængt 3 klokker. Den ene skulle kongen bruge til kanonstøbning og en anden er i brug i dag.
Døbefonten og alterbordsstenen er det eneste inventar fra middelalderen – ca. 1050 – 1540 – som er bevaret. De 2 lysestager på alterbordet er en gave fra ejerne af Kornumgård i 1596. De 2 lysekroner i skibet er fra omkring år 1900. På alteret står en syvarmet lysestage. I 1600-tallet fik kirken ny altertavle og prædikestol, som er bevaret. Altertavlen blev restaureret med tilføjelser og ændringer i 1913. Prædikestolen blev renoveret i 1669. Op til 1974-76 var der levende lys i kirken, kun ved orglet blev der opsat en elektrisk læselampe, da elektriciteten blev tilgængelig.
I 1974-1976 fik kirken en gennemgribende restaurering. Det gamle orgel blev udskiftet.
Gennem tiderne har det været vanskeligt at holde kirken i god stand. Der har været mange reparationer, ikke mindst hvad tårnet angår. Det blev i 1700-tallet revet ned og erstattet af en klokkestabel. I den vestlige ende af kirken har der engang været et pulpitur, en slags balkon.
De velhavende familier i sognet havde deres egne pladser i kirken. Jens Andersen Kjærulf og hustru Anna Griis havde deres adelsvåben på stolene, og Helmig Galskyt fra Kornumgård forærede i 1682 kirken et ligklæde for til gengæld at beholde de 2 øverste stole – henholdsvis en kvinde- og en mandsstol.
I kirkens nordside ved den tilmurede kvindeindgang ses mærkerne efter det gravkapel, som familien Galsskyt, Kornumgård, lod opføre omkring år 1679. Det blev igen nedrevet i 1855. Men gennem århundreder har der også været begravelser inde i kirken.
I kirken opbevares 2 gravsten fra 1700-tallet.
Helt op mod 1900-tallet var det almindeligt, at begravelsesritualerne foregik i den dødes hjem og på kirkegården. Den døde forblev i hjemmet, indtil begravelsen skulle foregå.
I 1913 opførtes et ligkapel i den vestlige ende af kirkegården, ikke langt fra det sted, hvor der indtil 1888 lå en skole, som blev nedrevet, fordi kirkegården skulle udvides.
I 1687 kom kirken under godset Birkelse med ejeren Otto Skeel. Kirken forblev under stamhuset Birkelse, hvor slægten Skeel stadigvæk var ejere, da kirken i 1912 blev selvejende.
Brønderslev bys vækst i 1880erne medførte, at den gamle kirke med dens cirka 200 pladser blev for lille, men først i 1922 kunne man indvie en ny kirke i Bredgade.