Początki i średniowiecze Stężyca rozwinęła się w miejscu o dużym znaczeniu komunikacyjnym, w pobliżu przeprawy przez Wisłę i dawnego ujścia Wieprza. W XIII wieku istniały tu osada targowa i przeprawa przez Wisłę. Funkcjonowała również parafia pod wezwaniem św. Marcina.
W literaturze przyjmuje się 1330 rok jako datę pierwszej lokacji miejskiej Stężycy. W dokumencie wystawionym w 1386 roku przez starostę sieciechowskiego i podczaszego królewskiego Spytka mieszkańcy Stężycy zostali określeni jako cives, czyli mieszczanie. W 1442 roku Władysław III Warneńczyk wystawił dla Stężycy przywilej na prawie magdeburskim. Wiązał się on prawdopodobnie z ponownym urządzeniem miasta i jego przesunięciem w bezpieczniejsze miejsce po zmianach koryta Wisły i wcześniejszych zniszczeniach nadrzecznej części osady.
W XIV i XV wieku Stężyca stopniowo przejęła część funkcji administracyjnych wcześniejszego ośrodka w Sieciechowie. Z prawobrzeżnej części dawnej kasztelanii sieciechowskiej wykształcił się powiat, a następnie ziemia stężycka, należąca do województwa sandomierskiego. Stężyca stała się siedzibą sądów szlacheckich i jednym z głównych ośrodków administracyjnych północno-wschodniej części historycznej Małopolski.