Pierwszy murowany dwór w Staromieściu wybudowany został prawdopodobnie w drugiej połowie XVIII w. przez nieznanego architekta, zapewne towarzyszył mu park. W połowie XIX w. dwór otoczony był niewielkim parkiem (widocznym na planie katastralnym z 1849 r.) Park usytuowany był w pd.-wsch. części założenia dworskiego i graniczył od północy i zachodu z zabudowaniami gospodarczymi. Powierzchnia parku zmieniała się, gdyż sukcesywnie przyłączano do niego nowe obszary. W 1878 roku majątek Staromieście wraz z Miłocinem i Ruską Wsią został zakupiony przez rodzinę Jędrzejowiczów i pozostał ich własnością aż do 1944 r. W latach 80. XIX w. został opracowany przez znanego, krakowskiego architekta Tadeusza Stryjeńskiego, projekt gruntownej przebudowy dotychczasowego dworu. Tadeusz Stryjeński był także prawdopodobnie autorem koncepcji zagospodarowania całości założenia, w tym także parku. Park został poszerzony w kierunku zachodnim aż do drogi prowadzącej z Rzeszowa do Sokołowa Małopolskiego. Z tego traktu prowadziła do pałacu aleja dojazdowa usytuowana na osi pałacu. Na planie katastralnym z pocz. XX w. widoczna jest ponadto ścieżka okalająca polanę główną parku w jego zachodniej części a także gazon z podjazdem podkreślający osiowość bryły pałacu i zachodniej części parku. Północną granicę parku stanowiła droga wydzielająca część gospodarczą, łącząca trakt na Sokołów z drogą prowadzącą przez wieś Staromieście.

Zasadnicze zmiany w rozplanowaniu i funkcji założenia pałacowo-parkowego przyniosła druga połowa XX wieku. W 1944 r. majątek Jędrzejowiczów został przejęty na rzecz Skarbu Państwa. Park z pałacem, jako przekazano miejscowej spółdzielni „Jedność”, która prowadziła w przekazanym obiekcie produkcję ogrodniczą. W parku urządzono boisko sportowe z torem żużlowym, a w zachodniej części parku - plac do zabaw tanecznych. W 1954 r. teren dawnego zespołu dworsko-parkowego przekazano szpitalowi – nastąpiły wówczas nieodwracalne zmiany w parku. Nowa droga prowadząca od strony ulicy Rycerskiej podzieliła park na dwie części wydzielone ogrodzeniami: wschodnią, funkcjonującą jako park dla pacjentów szpitala przeciwgruźliczego i zachodnią, przylegającą od południa do budynku szpitala miejskiego. W latach 90. XX w. wybudowano nowe skrzydło szpitala wzdłuż drogi dojazdowej, niejako „w poprzek” dawnego parku. W ten sposób zmienił się obszar i granice parku, jego kompozycja została przekształcona, pojawiły się elementy degradujące przestrzeń dawnego założenia.