Arkeologiska fynd visar att den första kyrkan troligen var en stavkyrka av trä. Senast omkring år 1160 ersattes den av en stenkyrka, som senare byggdes om och utvidgades flera gånger. Under 1400-talet fick kyrkan bland annat vapenhus, tegelvalv och ett torn av trä. Fram till reformationen fungerade den som moderkyrka för kyrkorna i det nya Halmstad.
På 1320-talet flyttades staden till sitt nuvarande läge vid Nissans mynning. Det gamla Halmstad började därefter kallas Övraby, den övre byn, och blev så småningom en egen socken och församling.
Under Nordiska sjuårskriget brändes Övraby ner av den svenska armén år 1563. Även Vårfrukyrkan förstördes och lämnades sedan att förfalla. Kyrkans silver räddades och kyrkklockan fördes till S Nikolai kyrka i Halmstad.
Ruinen grävdes ut under 1930-talet under ledning av landsantikvarien Erik Salvén. Vid en ny arkeologisk undersökning 1978 hittades spår efter de kraftiga stolpar som tros ha burit den äldre träkyrkan. Stenkyrkan var byggd av gråsten och mätte omkring 28 gånger 9 meter, inklusive kor och vapenhus.