Pierwotnie na działce lokacyjnej nr 5 znajdowała się drewniana karczma należąca do książąt Sanguszków. Barokowy budynek pałacowy został wzniesiony w latach 1785–1796 lub do 1799 roku z inicjatywy ówczesnego właściciela miasta, Hieronima Sanguszki. Książę Hieronim Sanguszko zamieszkał w nim na stałe od 1798 roku. Na początku XIX wieku syn Hieronima, książę Eustachy Sanguszko, sprzedał budynek władzom austriackim, które umieściły w nim w 1825 roku siedzibę cyrkułu , obwodu,  od 1867 roku powiatu.

Ogromny, jak na Tarnów, budynek został wybudowany w stylu barokowym. W 1836 w pałacu zamieszkał starosta tarnowski  Józef Breinl von Wallerstern.

W czasie rzezi galicyjskiej na plac obok budynku chłopi zwieźli ok. 150 ofiar, a także przyprowadzili pojmanych powstańców krakowskich celem oddania ich władzom austriackim. Za wierność cesarzowi  starosta Breinl w ramach nagrody wypłacił chłopom 4000 złotych reńskich.

W XIX wieku budynek co najmniej dwukrotnie przebudowywano. Po raz pierwszy przed 1831 rokiem, kiedy to budynkiem zarządzało Starostwo Tarnowskie. Nadano mu formy klasycystyczne, o wieloosiowej fasadzie z obszerną sienią pośrodku. Podczas przebudowy w 1870 roku, formy klasycystyczne zostały zaburzone. Około 1900 lub 1901 roku budowla po raz kolejny została przebudowana, uwzględniając przede wszystkim fasadę, której nadano neobarokowy wygląd. W XX wieku na polecenie władz austriackich, na podstawie projektu Szczęsnego Zaręby, dyrektora budownictwa miejskiego Tarnowa, ujednolicono charakter budynku na zbieżny z ówczesną estetyką.

W czasach austriackich budynek był jednym z najważniejszych obiektów publicznych w mieście, spotykali się w nim z mieszkańcami  np. namiestnicy guberni i arcyksiążęta.

W  1918 roku pałac został zajęty przez członków Komitetu Samoobrony, którzy zmusili starostę austriackiego do złożenia przysięgi wierności wobec polskiego rządu. W latach 1918–1939 w budynku mieściło się starostwo powiatowe, a czasie II wojny światowej stał się jedną z siedzib niemieckich władz okupacyjnych. Od zakończenia wojny do 1975 roku budynek ponownie mieścił władze powiatowe – Powiatową Radę Narodową, a następnie do roku 1990 był siedzibą wydziałów urzędu wojewódzkiego województwa tarnowskiego. W latach 1990–1998 znajdował się w nim urząd rejonowy. Od 2004 lub 2005 roku budynek jest własnością prywatną i nie jest użytkowany.