AltDet tyderer påtidligere blevet antaget, at kvaderstenskirken blev ødelagt i forbindelse med kampene mellem [[Erik Plovpenning]] og [[Abel af Danmark|Abel]] i 1247, men der er ingen dokumentation for, at disse kampe overhovedet berørte kirken. Der er nærmere tale om, at man rev den gamle og denssandsynligvis alt for beskedne kirke ned med henblik på at opføre en kirke af en størrelse og et udseende, der passede til en ekspanderende by. Kvaderstenskirkens afløser, en stor teglstenskirke i blandet [[romansk stil|romansk]]-[[gotik|gotisk]] stil, synes at være blevet opført kort tid efter. Stilmæssigt har denne kirke mindet om de ældste dele af Aabenraa Skt. Nikolai kirke og til dels cistersienserkirken i Løgumkloster.
Man kan endnu gøre sig en forestilling om dens ydre ved at betragte den nuværende kirkes [[Kirkeskib (bygningsdel)|tværskib]], der er bygget af store gule og lyserøde [[munkesten]], der let lader sig udskille fra senere ændringer og tilbygninger, hvis sten er mørkerøde. Den søndre [[gavl]] er den bedst bevarede bygningsdel fra denne periode.
Henimod 1270 fandt der en betydelig ombygning sted. Kirken blev nu eten såkaldt [[hallekirke]] efter nordtysk forbillede, med to [[Kirkeskib (bygningsdel)|sideskibe]], hvis bredde svarede til halvdelen af hovedskibets. Kirken fik derved en ganske anselig størrelse, og udvidelsen hænger utvilsomtutvivlsomt sammen med, at Vor Frue Kirke i Haderslev havde fået status af [[Domkapitel|kollegiatkirke]] i forhold til domkirken i [[Slesvig by|Slesvig]]. Som sådan nævnes den første gang i 1273, da den fik skænket Slesvig-bispens tiende af Aller sogn. Det var herefter blevet nødvendigt med plads til en række altre til kollegiatkapitlet, som kirkens præsteskab fra nu af kaldtes.
