W połowie X wieku na wyspie zwanej Regia powstał drugi warowny gród. Wiślica w XI wieku składała się więc z dwóch grodów, z których jeden stale obsadzony przez drużynę książęcą, miał typowo militarny charakter. Pomiędzy nimi rozwijała się osada handlowa z kościołem grodowym. W XI wieku zbudowano kościół św. MikołajaE. Dąbrowska, Studia nad osadnictwem wczesnośredniowiecznym ziemi wiślickiej, Wrocław 1965, s. 44 nn.K. Żurowska, Kościół św. Mikołaja w Wiślicy na tle romańskich jednonawowych budowli sakralnych, [w:] Wiślica. Nowe badania i interpretacje, s. 57–60.. Pod koniec XI wieku osada została spalona, nie zatrzymało to jednak jej rozwoju. W 1135 Wiślica została zniszczona, być może splądrowana przez Rusinów i Połowców (szczegóły tego wydarzenia wymagają dalszych badań). Po śmierci Bolesława Krzywoustego i rozbiciu dzielnicowym Wiślica znalazła się w dzielnicy sandomierskiej.
Za panowania księcia Henryka Sandomierskiego Wiślica stała się ponownie jednym z najważniejszych małopolskich miast. Po weryfikacji wcześniejszych badań stwierdzono, że wszystkie budowle kamienne na Regii powstały nie wcześniej niż w drugiej połowie XII wieku. Książę ufundował w Wiślicy zgromadzenie kanoników oraz pierwszą wiślicką kolegiatę.