Szükségességét már 1895-ben felvetették az akkori Nyitrai Hírlapban, és a magyar igazságügyi minisztérium egy évvel később jóvá is hagyta, hogy a városban igazságügyi palota épüljön. A szecessziós stílusú épületet Kiss István tervei alapján 1901 és 1903 között a Tomaschek és Csellágh cég építette fel, 1904-ben pedig átadták a háromszáz férőhelyes börtönt is. Az első években egyáltalán nem volt telt ház, alig 120-150 személyt tartottak itt fogva, mert a súlyosabb bűncselekményekért elítélteket még mindig a közeli Lipótvárra vitték. Nyitrán általában a tolvajok és verekedők raboskodtak, jobban mondva művelték a börtönhöz tartozó kertet és a fegyház által bérelt földeket, takarították az udvart, és fát vágtak, hogy legyen mivel fűteni a cellákat. 1923-ig petróleumlámpákkal világítottak, és a falba épített kemencékben fűtöttek – a rabok évente tizenhét vagon fát aprítottak fel. A második világháborúban az épületet bombatalálat érte, de a cellákat továbbra is használni lehetett, így a lakóik is maradtak, csak a Vörös Hadsereg parancsnokai engedtek 1945. március 31-én mindenkit szabadon. Néhány hónapig fogolytáborként működött a nyitrai börtön, aztán a politikai foglyok számára jelölte ki az Állambiztonsági Hivatal. Miután 1960-ban ez a rossz emlékű hivatal beszüntette tevékenységét, a börtönépületbe az állami levéltár költözött, és 1970-ig ott is maradt. Mivel az ország fegyintézeteiben ekkortájt ismét kevésnek bizonyult a férőhely, 1971-ben elkezdték a régi nyitrai börtön felújítását, és 1973. szeptember 1-jétől újra eredeti rendeltetésének megfelelően használják az épületet. Azóta többször is bővítették, átalakították, irodaépületet és a fegyőrök képzését szolgáló szakközépiskolát építettek hozzá. Jelenleg 417 elítélt, köztük 13 nő tölti itt a büntetését.