Najstarsza świątynia w Gorzowie Wielkopolskim została wzniesiona pod koniec XIII w. jako miejski kościół parafialny. Zbudowana została na planie trzynawowego, pseudobazylikowego korpusu z wieżą przy elewacji zachodniej oraz zakrystią w kształcie prostokąta przy elewacji północnej. Pierwotnie nosiła tytuł Maryi Panny i 11 Dziewic. Początkowo patronat nad kościołem sprawowało miasto, od 1299 r. kapituła kolegiaty w Myśliborzu, a następnie zakon krzyżacki oraz brandenburscy elektorzy.
Gorzowska katedra, zgodnie z założeniami tradycji chrześcijańskiej, zbudowana została w specyficzny sposób. Prezbiterium musiało być zwrócone ku wschodowi, skąd w dniu Sądu Ostatecznego przybędzie Chrystus, główne wejście natomiast znajdowało się zawsze od zachodu, naprzeciw głównego ołtarza.