Architektura Świątynia została wzniesiona z kamienia ciosowego. Wyjątkiem jest ceglany szczyt fasady zachodniej, który jest efektem odbudowy ze zniszczeń wojennych w latach 20. XX w. Kościół ma budowę pseudonawową. Wielobocznie zamknięte prezbiterium jest niższe i węższe od nawy. Od północy przylega do niego przybudówka z 2. połowy XVII w. w której znajdują się zakrystia i skarbiec. Główne wejście do kościoła znajduje się od strony południowej. Do wnętrza budowli prowadzi ostrołukowy portal, którego drzwi okute są w skośną kratę z antabą i ozdobione rozetą z XV w.
thumb|266px|left|Tablica erekcyjna z królem Kazimierzem Wielkim
Nad portalem umieszczona jest płaskorzeźbiona tablica erekcyjna z przedstawieniem Kazimierza Wielkiego. Król klęczy przed Madonną z Dzieciątkiem ofiarowując jej model świątyni. Za nim znajduje się postać biskupa krakowskiego Bodzanty. Tablica powstała w 1464, przeszło sto lat po ufundowaniu kościoła. Inicjatorem upamiętnienia fundacji był Jan Długosz, który pełnił w Wiślicy funkcję kanonika.
Północny portal kościoła pochodzi z 2. połowy XIV w. W portal wmurowane są rzeźbione herby: dwa Orły Piastowskie oraz herb Wielkopolski.