I 1840 nedsatte Christian 8. en kommission om tugt- og forbedringshuse, og i 1859 åbnede forbedringshuset i Vridsløselille med 57 indsatte mænd. Bygningen blev opført efter det panoptiske system med fangegange ud fra et centralt overvågningsrum. De indsatte var indtil 1930 i total isolation og måtte ikke tale sammen. Fra 1933 rummede institutionen fængselsfanger.
I 1935 tilføjedes Anstalten ved Herstedvester (i dag Herstedvester Fængsel) som såkaldt psykopatforvaring. Bygningerne blev opført på den anden side af Roskildevej, men var organisatorisk under Statsfængslet frem til 1971.
Blandt kendte fanger i Statsfængslet har været socialisten Louis Pio, justitsminister P.A. Alberti og politimorderen Palle Sørensen. Den mest spektakulære fangeflugt skete d. 27. august 1995, da en gummiged på 36 tons brød gennem fængselsmuren, og 13 fanger undslap.
Fængslet lukkede i 2016 og rummede frem til 2018 frihedsberøvede asylansøgere.
Indgangen til fængslet er et kendt motiv fra Olsen-banden-filmene, idet de ofte begynder og slutter der. Vejen foran fængslet skiftede i 2004 navn fra Fængselsvej til Egon Olsens Vej efter fængslets berømte fiktive fange.
