New Jerseyn osavaltiovankila on kompleksi, joka koostuu kolmesta erillisestä mutta toisiinsa yhteydessä olevasta fyysisestä laitoksesta, jotka ovat peräisin kolmelta eri aikakaudelta, jolloin vankiloita rakennettiin tontilla. Nämä kolme osaa ovat vuoden 1798 Penitentiary House, vuoden 1832 Fortress Penitentiary ja vuoden 1982 nykyvankila.
NJ Penitentiary House vuodelta 1798, joka oli New Jerseyn ensimmäinen osavaltiovankila ja Philadelphiassa sijaitsevan Walnut Street Jailin ja New Yorkissa sijaitsevan Newgaten jälkeen valtakunnan kolmas osavaltiovankila New Jerseyn osavaltiovankiloista, on myös vanhin rakennus, joka on yhä toiminnassa aktiivisen, toiminnassa olevan vankeinhoitovankilan osana Yhdysvalloissa. Tämän ansiosta NJSP voi väittää olevansa Yhdysvaltojen vanhin jatkuvasti toiminnassa oleva osavaltion vankila. Vuoden 1798 vankilarakennuksen ainoa säilynyt osa on alkuperäinen Front House, joka toimi alun perin asuintiloina osavaltion vankilan vartijalle, neljälle apulaisvartijalle (neljä ensimmäistä miestä, jotka toimivat nykyisin osavaltion vankeinhoitovirkamiehinä), asevarastolle, hallinnollisille toimistotiloille ensimmäisessä kerroksessa ja kellarissa sijainneelle selliriville häiritsevien vankien vangitsemista varten. Koska Penitentiary House lakkasi majoittamasta vankeja muutama vuosi sen jälkeen, kun Fortress Penitentiary avattiin vuonna 1832, Auburn Correctional Facility voi väittää olevansa Yhdysvaltojen vanhin yhtäjaksoisesti toiminnassa ollut sellirakennus.
Valmistumisen ja Penitentiary Housen vankien siirtämisen jälkeen John Havilandin suunnittelemaan uuteen Fortress Penitentiary -yhdyskuntaan vuonna 1836 vuoden 1798 laitos toimi vuorotellen Mercerin piirikunnan vankilana, kun heidän työtaloaan rakennettiin Titusvilleen, NJ:n osavaltioon, ja sen jälkeen osavaltion asevarastona vuoteen 1929 asti, jolloin kaikki siellä sijainneet kansalliskaartin varusteet ja palvelut siirrettiin vastavalmistuneeseen ANG:n tukikohtaan Sea Girtiin, jolloin tyhjän yhdyskunnan määräysvalta palautettiin osavaltiolliselle vankilalle. Vuonna 1930 kaikki Penitentiary Housen rakennukset purettiin lukuun ottamatta Front Housea, joka muutettiin osavaltion vankilan vartijan asunnoksi. Raivattu maa-alue, jolla rangaistuslaitoksen sellitalot ja myymälärakennukset olivat aiemmin sijainneet, ympäröitiin 22 metriä korkealla teräsbetoniseinällä, ja se avattiin vuonna 1930 Big Yardina. Tämä uusi, suuri virkistyspiha helpotti ahtaita oloja päärakennuksen muurien sisäpuolella, jossa oli siihen asti ollut vain vähän tilaa ulkovirkistykseen.
New Jerseyn osavaltion vankilan toiseksi vanhin osa, Fortress Penitentiary, rakennettiin vuosien 1832 ja 1836 välisenä aikana, kun viereisen Penitentiary Housen vangit siirrettiin sinne. Vuoden 1832 laitos rakennettiin osavaltion jo omistamalle ja Penitentiary Housen hallinnassa olleelle vierekkäiselle tontille osavaltion vankilan vartijan valvonnassa, ja siinä käytettiin vankien työvoimaa neljän vuoden rakentamisen aikana. Näin ollen vuoden 1836 Fortress Penitentiary -rakennusta pidetään kiinteistöllä sijaitsevan osavaltion vankilan lisäosana. Tämä väite on perusteltu, koska nämä kaksi laitosta sijaitsivat samalla kiinteistöllä ja koska vartija hallinnoi ja valvoi niitä vankilakompleksina, jossa työskenteli ja majoittui sama vankilaväestö. Koska osavaltion vankilaa käytetään nykyään yhtenä kokonaisuutena, joka koostuu erillisistä erillisistä tiloista, tämä päätelmä on perusteltu.
Vuonna 1917 valmistuneessa maisterintutkielmassaan, joka julkaistiin nimellä ”History of the Penal, Reformatory and Correctional Institutions of New Jersey” (New Jerseyn rangaistuslaitosten, parannuslaitosten ja oikaisuinstituutioiden historia) edesmennyt tunnettu yhdysvaltalainen historioitsija, tohtori Harry Elmer Barnes, julkaisi historiansa ja analyysin New Jerseyn osavaltiollisten vankiloiden, parannuslaitosten ja rangaistuslaitosrakennelmien historiasta ja analyyseistä kyseiseen ajanjaksoon mennessä. Hänen teoksensa oli analyysi eri rangaistusfilosofioiden soveltamisesta ja niiden onnistumisista, epäonnistumisista ja muutoksista vuosina 1798-1917. Hän erotti teoksessaan Penitentiary Housen ja vuoden 1832 Fortress Penitentiaryn kahdeksi ”järjestelmäksi”. Tohtori Barnesin käyttämää termiä ”järjestelmä” käytettiin tuohon aikaan samalla tavalla kuin me käytämme nykyään termiä ”Paradym” – hänen teoksensa ”First Prison System in NJ” (ensimmäinen vankilajärjestelmä NJ:ssä) sovellettuna Penitentiary Houseen ja ”Second Prison System in NJ” (toinen vankilajärjestelmä NJ:ssä) sovellettuna vuoden 1832 laitokseen ei kuvaillut kahta erillistä vankilaa eikä osoittanut kahta erillistä vankeinhoitolaitosta.
Tämä oli historiaa ja kuvaus New Jerseyn siirtymisestä pois Congregate-järjestelmästä, jossa kaikki henkilöt ikään, sukupuoleen tai mielentilaan katsomatta yksinkertaisesti suljettiin Penitentiary Houseen, Pennsylvanian vankilajärjestelmään, jossa vankeja pidettiin yksittäisissä selleissä täysin eristyksissä muista vangeista ja vartijoista. Valtion vankilan auktoriteetti ja hallinto virastona ei muuttunut – vartija virastopäällikkönä valvoi Penitentiary House -rakennusta, valvoi ja osallistui vankityövoiman käyttöön Fortress Penitentiaryn rakentamisessa vuosina 1832-1836 ja valvoi kaikkien vankien siirtoa vanhasta vankilasta uuteen vankilakompleksiin vuonna 1836 ja jatkoi uudessa vankilakompleksissa. Tämä rakentaminen, siirto ja toiminnan jatkaminen kiinteistön toiselta puolelta toiselle luo yhteyden vanhan ja uuden vankilan välille ja osoittaa, että New Jerseyn osavaltion vankila on ollut olemassa ja toiminut jatkuvasti samassa paikassa vuodesta 1798 lähtien. Näin ollen tohtori Barnes kuvasi rangaistusteorian ja -käytännön muutosta, ei vanhojen rakennusten ja hallintoelimen lakkauttamista ja uuden tilalle asettamista. Toiminnassa tai hallinnossa ei tapahtunut katkosta.
Vuonna 1832 rakennettua laitosta laajennettiin useita kertoja 1800-luvun aikana, ja vuosina 1859-1907 rakennettiin uusia siipiä ja myös suurempia myymälähallirakennuksia. Vuosina 1895-96, kun 6-siipi rakennettiin, alkuperäiset seinät ulotettiin vanhan Penitentiary House -rakennuksen kulmiin, jotta tämä siipi sekä uudempi Shop Hall -rakennus, joka tähän asti oli ollut päämuurien ulkopuolella, saatiin ympäröityksi.
Huumausrangaistukset siirrettiin piirikuntien vankiloista NJ:n osavaltion vankilaan vuonna 1907, jolloin ensimmäinen teloitus suoritettiin uudella sähköisellä tuolilla, jonka oli rakentanut Trentonissa asuva Carl Adams Adamsin Adams Electric Company -yhtiönsä myymälöissä. Viimeinen sähkötuomio suoritettiin vuonna 1963. Vuonna 1979 kuolemanvankila (8-siipi) ja vanha sairaalasiipi purettiin, jotta tilaa voitiin tehdä uudelle liikuntasalille.
Nykyaikaisen rakennuksen pohja rikottiin vuonna 1979, ja se valmistui vuonna 1982. Sen jälkeen ei ole tehty mitään lisäyksiä.