Świątynię według nowożytnej płyty inskrypcyjnej wybudowano w 1082 z fundacji Władysława Hermana, jednak w rzeczywistości pochodzi ona prawdopodobnie z XII w. i jest fundacją Bolesława Krzywoustego. Świątynię wymienia również Jan Długosz, podając rok 1086 jako datę fundacji. Równocześnie z kościołem powstał na tej samej górze klasztor Benedyktynek, który został w 1241 zburzony podczas najazdu tatarskiego. Nosi on cechy typowe dla architektury obronnej. Po powstaniu kościoła pw. św. Michała w 1520 starsza świątynia straciła znaczenie i zaczęła podupadać. W 1793 kościół został ograbiony przez żołnierzy pruskich, a następnie zamieniony na magazyn zbożowy. Na początku XX wieku świątynia była zniszczona, a jej dach pokryty był słomą. Prace restauracyjne rozpoczęto z inicjatywy cara Mikołaja II. Kolejne zniszczenia zostały spowodowane przez I wojnę światową. Pierwsze, nieukończone prace rekonstrukcyjne prowadzono w latach 1924-1926. Ostateczny wygląd nadała mu restauracja prowadzona z inicjatywy prezydenta Ignacego Mościckiego, według projektu Wilhelma Henneberga. Wprowadzono wtedy wiele elementów obcych wcześniejszej architekturze kościoła m.in. podwyższono o jedną kondygnację wieżę, a w nawie od strony zachodniej na miejscu otwartej arkady wybudowano emporę.
