Kalėjimų departamentas Lietuvoje buvo įsteigtas 1919 m. vasario 11 d.
 
Tarybinės okupacijos metais Lietuvos kriminalinių bausmių vykdymo sistema buvo įtraukta į bendrą Tarybų Sąjungos kriminalinių bausmių vykdymo sistemą, pavaldžią Vidaus reikalų ministerijai. Kalėjimų departamentas pervadintas Pataisos darbų įstaigų valdyba, vėliau – Pataisos reikalų valdyba. 

1990 m. atkūrus Lietuvos Nepriklausomybę, Pataisos reikalų valdyba perorganizuota į Pataisos reikalų departamentą. 

Vykdant teisinės sistemos reformą, 2000 m. rugsėjo 1 d. Lietuvos kriminalinių bausmių vykdymo sistema perduota iš Vidaus reikalų ministerijos valdymo srities į Teisingumo ministerijos valdymo sritį. Pataisos reikalų departamentui grąžintas nepriklausomos Lietuvos tarpukario laikais turėtas pavadinimas – Kalėjimų departamentas prie Lietuvos Respublikos teisingumo ministerijos. Po reorganizavimo, nuo 2023-01-01 įstaiga tapo - Lietuvos kalėjimų tarnyba. 

Šiai institucijai 1990–2001 metais vadovavo Jonas Blaževičius. Teisingumo ministro įsakymu 2002 m. birželio 17 d. Kalėjimų departamento laikinuoju vadovu tapo Skirmantas Agurkis. Nuo 2003 m. balandžio 22 d. iki 2005 m. vasario 18 d. Kalėjimų departamentui vadovavo Rimvidas Kūgis. Nuo 2005 m. balandžio 28 d. iki 2011 m. liepos 12 d. Kalėjimų departamento direktoriaus pareigas ėjo Saulius Vitkūnas. Nuo 2011 m. liepos 12 d. iki 2012 m. sausio 23 d.  Kalėjimų departamentui laikinai vadovavo direktoriaus pavaduotojas Kęstutis Širvaitis. Nuo 2012 m. sausio 24 d. iki 2014 m. gruodžio 8 d. Kalėjimų departamento direktoriaus pareigas ėjo Artūras Norkevičius. Nuo 2015 m. sausio 12 d. Kalėjimų departamentui laikinai vadovavo Živilė Mikėnaitė, kuri nuo 2015 m. birželio 1 d. iki 2017 m. kovo 27 d. ėjo Kalėjimų departamento direktoriaus pareigas. Nuo 2017 m. gruodžio 22 d. iki 2019 m. vasario 7 d. Kalėjimų departamento direktoriaus pareigas ėjo Robertas Krikštaponis.

Nuo 2019 m. gegužės 10 d. į Kalėjimų departamento direktoriaus pareigas paskirtas Virginijus Kulikauskas. Nuo 2023-01-01 tęsia darbą Lietuvos kalėjimų tarnybos direktoriaus pareigose.