Den store og rigt udstyrede Vrejlevkloster Kirke er ældre end selve klosteranlægget, idet den er bygget i ca. 1160, måske som et dobbeltkonvent af præmonstratenserordenen. Den romanske kirke, der er indviet til Sankt Nikolaus, var en elegant kvaderstensbasilika. For at give plads til korherrerne var kirken forsynet med et ganske langt kor; midtskibets vægge var båret af fem søjlepar. Adgangen til kirken skete fra døre mod nord og syd. De var placeret forholdsvis langt fra vestgavlen, således at der var plads til et pulpitur for nonnerne i vest. Kirkens nuværende udseende stammer fra en stor ombygning i anden halvdel af 1400-tallet, hvor det nordre sideskib blev forhøjet, det søndre nedrevet, og koret blev forlænget og udvidet. Med inspiration fra Børglum blev smukke stjernehvælv tillige indsat i hovedskibet.
