A Tolna Megyei Büntetés-végrehajtási Intézet Szekszárd történelmileg híres - I. Béla királyról elnevezett - terén helyezkedik el. Az 1880-as évek végén több éven keresztül húzódott egy új börtön építésének ügye. A fejlődő, polgárosodó megyeszékhely Szegzárd, kezdte kinőni a vármegyeháza bizonyos helyiségeiben működő törvénykezési hivatalokat, továbbá a fogház céljaira szolgáló helyiségek sem feleltek meg a kor követelményeinek, bár akkor már állt az 1845. április 15-én alapított dologház, rabdolgoztató néven említett épület a vármegyeháza mellett. Kétszáz évig a megyeházában lévő fogház szolgáltatta az igazságot, míg elhatározták, hogy az új bíróság mellé megépítik a királyi ügyészségi fogházat. 1890. október 21-ei megyegyűlésen a mostani épületkomplexum helyén álló épületeket és területet átadták a Királyi Igazságügyi Kincstárnak. Wagner Gyula mérnök tervei alapján épült fel az un. Igazságügyi Palota, kb. 1891-ben. Ezen épületegyüttes 1/5-öd részén került kialakításra a börtön, melyben a vizsgálati fogságban lévő személyeket helyezték el. Ekkor az elítéltek még a régi vármegyeházában maradtak.
Az új – minden szempontból modern, a szükségleteket korszerűen kielégítő, tágas – fogház 1849 augusztusától, 3 hónap alatt került tető alá. Átadására 1895. szeptember 20-án került sor, ahova a foglyok 23-án költöztek át. Érdekessége, hogy a városban itt volt először villanyvilágítás és vezetékes víz az épületben, illetve itt került kialakításra elsőként forró vizes központi fűtés rendszer. Az épület tetőszerkezete ismeretlen körülmények között 1896. május 18-án leégett, melyet csak több havi késedelemmel építettek újjá. A felújítást követően a külsejében impozáns, az ügyészségi, bírósági épülettel egybe épült, környezetébe, a városképbe beleillő épület született. Belső kialakítását illetően az akkori kor klasszikus börtönépítészeti jegyeit hordozta magán. Körfolyosós rendszerű, a zárkák ajtói erre a folyosóra nyílnak, a zárkák ablakai az udvarra néztek, tehát a fogvatartottak elhelyezésére szolgáló részei közterülettel szinte nem is érintkeznek.
