Kalėjimų departamentas Lietuvoje buvo įsteigtas 1919 m. vasario 11 d.

Sovietų okupacijos metais Lietuvos kriminalinių bausmių vykdymo sistema buvo įtraukta į bendrą Sovietų 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, ir dabar oficialus jo pavadinimas - Kalėjimų departamentas prie Lietuvos Respublikos teisingumo ministerijos.

Š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 2002 m. gruodžio 12 d. Kalėjimų departamento direktoriaus pareigas laikinai eiti buvo pavesta departamento direktoriaus pavaduotojui Ramūnui Kalendrai. Nuo 2003 m. balandžio 22 d. iki 2005 m. vasario 18 d. Kalėjimų departamentui vadovavo Rimvidas Kūgis. Teisingumo ministro įsakymu nuo 2005 m. vasario 21 d. Kalėjimų departamento direktoriaus pareigas laikinai eiti pavesta direktoriaus pavaduotojui Sauliui Vitkūnui. Laimėjęs konkursą, S. Vitkūnas nuo 2005 m. balandžio 28 d. buvo paskirtas Kalėjimų departamento direktoriumi.

Departamentas turi 15 jam pavaldžių įkalinimo įstaigų, kurios vykdo kardomąjį kalinimą (suėmimą) ir laisvės atėmimo bausmę, 49 teritorines pataisos inspekcijas, kurios vykdo bausmes, nesusijusias su laisvės atėmimu, ir lygtinai paleistų iš laisvės atėmimo vietų prieš terminą asmenų priežiūrą, ir Mokymo centrą, kuriame mokomas naujai priimti į tarnybą departamentui pavaldžiose įstaigose darbuotojai.

Prie 3 įkalinimo įstaigų veikia valstybės įmonės, kurių savininko teises ir pareigas įgyvendina Kalėjimų departamentas. Valstybės įmonėse įdarbinami nuteistieji. Šiose įmonėse gaminami baldai, elektros instaliacijos detalės, durų ir langų apkaustai, įvairūs liejiniai iš metalo, siuvama patalynė, darbiniai drabužiai, gaminama darbinė avalynė, remontuojami automobiliai. Nuteistųjų pagaminta produkcija savo kokybe nenusileidžia tokios pat rūšies produkcijai, pagamintai kitose įmonėse, ir dažnai yra pigesnė.