Bazylika romańska, tzw. św. Gereona

W bezpośrednim sąsiedztwie książęcego palatium, po jego zachodniej stronie, na miejscu starszych budowli powstała jeszcze w XI wieku bazylika – być może najstarszy romański kościół w Małopolsce. Do niedawna uważana była za pierwszą katedrę romańską, pochodzącą (lub przynajmniej zaczętą) z czasów Bolesława Chrobrego. Po odkryciach resztek budowli przedromańskich, zarówno pod tą bazyliką, jak i pod kościołem katedralnym przyjmuje się późniejszy okres jej realizacji, wskazując na osobę księcia Kazimierza I lub też Bolesława Szczodrego jako fundatorów tego kościoła.

Kościół pełnił rolę nekropolii rodziny książęcej oraz jej otoczenia. W północnym ramieniu transeptu, na przeciwko ołtarza odkryto kamienny sarkofag, zawierający pochówek mężczyzny. Była to ważna osobistość, bowiem w wieku XIII, podczas remontu świątyni zaznaczono miejsce grobu płytą z piaskowca, umieszczoną w nowej posadzce. W ramieniu południowym odkryto zlokalizowany podobnie, na osi ołtarza, fundament, przeznaczony zapewne pod monumentalny sarkofag, wyniesiony ponad poziom posadzki. Inny kamienny grobowiec, wyrabowany, stwierdzono w obrębie nawy głównej kościoła,

Dyskusyjny problem stanowi określenie funkcji tego kościoła. Bezpośrednie sąsiedztwo z budynkiem pałacowym wskazywać może na reprezentacyjny, dworski charakter świątyni. Znaczna skala i bogaty program przestrzenny negują, w pewnym sensie, ściśle prywatny jej charakter. Być może, przynajmniej w zamyśle, była to budowla przeznaczona dla zgromadzenia zakonnego lub kanonickiego, ściśle powiązanego z dworem książęcym, na wzór kolegiaty św. św. Szymona i Judy w cesarskiej rezydencji w Goslarze, czy też kościoła św. Jerzego, przeznaczonego dla żeńskiego konwentu benedyktynek na grodzie praskim. Wspomnieć należy także o hipotezie postawionej przez Tomasza Węcławowicza, iż kościół ten mógł stanowić część założenia tzw. „katedry podwójnej”, występującej w okresie późnoantycznym oraz w średniowieczu na terenie wielu krajów Europy.