Syn Bolesława Krzywoustego, Henryk, żyjący w XII w., otrzymał we władanie Ziemię Sandomierską, a jego rezydencją stał się zamek w nadwiślańskim grodzie sandomierskim. Był to pierwszy książę polski, który wyruszył na wyprawę krzyżową do Ziemi Świętej. Z dalekiej wędrówki przywiózł ze sobą kobietę, którą bardzo kochał. Nie była ona księżniczką ani też nie pochodziła z królewskiego rodu. Była jedynie prostą Żydówką. Książę obdarował ja klejnotami, a w zamku sandomierskim urządził dla niej wspaniałe komnaty. Piękna Judyta miała wielki wpływ na księcia i to spowodowało, że rycerze, duchowieństwo i możni zmusili Henryka do usunięcia dziewczyny z miasta. Wcześniej jednak książę wydał tajny rozkaz, aby niewolnicy pod kierunkiem arabskiego budowniczego wznieśli podziemny pałac w okolicy wzgórza Salve Regina. Dziewczyna opuściła Sandomierz udając, że odjeżdża, aby następnie zawrócić i ukryć się w podziemnym pałacu. Świadków budowy usunięto i tylko książę znał do niego tajemne wejście. Legenda głosi, że pałac miał sto komnat, a niektóre z nich wysadzone były szmaragdami i diamentami. Jedzenie podawano na złotych talerzach. Tajemnicza Żydówka zajęła się czarami, a Henryk odwiedzał ją często przebywając w pałacu całymi tygodniami. Pewnego dnia ogłosił, że udaje się na wyprawę przeciwko pogańskim Prusom. W drodze porzucił rycerzy i przybył do ukochanej Judyty. Dzięki jej czarom otrzymał wieczną młodość i do dnia dzisiejszego przebywa w podziemnym pałacu razem ze swoją wybranką.