Předchůdcem Vězeňské služby ČR byl Sbor nápravné výchovy, který vznikl v resortu ministerstva vnitra ČSSR 15. 7. 1965. Od 1. 1. 1969 v rámci dělení kompetencí ve federativně uspořádaném státě přešel Sbor nápravné výchovy do resortu ministerstva spravedlnosti ČSR.
Pro realizaci zákona o výkonu trestu odnětí svobody č. 59/1965 Sb., který byl již koncipován podle doporučení vydaných OSN formou Standardních minimálních pravidel pro zacházení s vězni z roku 1957, bylo nezbytné usilovat o zvyšování kvalifikace vězeňského personálu, proto ministr spravedlnosti ČSR zřídil v roce 1970 resortní odbornou školu v Ostrově nad Ohří. Ta se téhož roku stala střední odbornou školou (dále jen SOŠ SNV), kterou již Institut vzdělávání VS ČR považuje za svou předchůdkyni, protože v té době se již zacházení s vězni opíralo více o vědecké obory kriminologie a penologie. Ve čtyřletém studijním oboru „15-2-02 – vychovatelství“ v letech 1970–1994 úspěšně maturovalo celkem 560 absolventů. Škola zabezpečovala také sedmitýdenní nástupní kurzy, v jejichž osnovách byly odborné předměty: nápravná výchova s metodikou, bojová a tělesná příprava, psychologie a pedagogika. V letech 1970–1980 ukončilo v Ostrově nad Ohří nástupní kurz 4738 příslušníků, z toho 354 žen.
V průběhu následujících let se několikrát měnilo organizační začlenění, sídlo i název školy. V roce 1975 se SOŠ SNV stala pobočkou nově založené Praporčické školy SNB v Brně. SOŠ SNV byla roku 1980 přemístěna nejprve do pobočky PŠ SNB v Zastávce u Brna. V letech 1980–1981 tam nástupní kurz ukončilo 530 příslušníků, z toho 35 žen. V roce 1982 se SOŠ stěhovala spolu s pobočkou Praporčické školy SNB do nově dokončeného školského areálu PŠ SNB v Brně, kde měla k dispozici šestipatrovou budovu s kabinety pro učitele a čtyřlůžkovými pokoji pro studenty. Osm učeben a specializované učebny byly v samostatné části areálu PŠ SNB. V letech 1982–1989 v Brně ukončilo nástupní kurz 2809 příslušníků, z toho 269 žen. Po listopadu 1989 nastala zásadní změna v pojetí vzdělávání pracovníků vězeňství v roce 1992, kdy byl přijat zákon o Vězeňské službě a justiční stráži č. 555/1992 Sb.
Roku 1992 se SOŠ SNV rozkazem ministra spravedlnosti transformovala v Institut vzdělávání Vězeňské služby. Délka nástupních kurzů byla stanovena na 3 až 10 týdnů podle náročnosti vykonávaného typu práce, příslušníkům vězeňské stráže byly kurzy prodlouženy na šestnáct týdnů a jejich součástí byla i řízená čtyřtýdenní praxe vykonávaná ve vybraných věznicích. Zároveň v Brně skládali maturitu příslušníci, kteří započali studium ještě před rokem 1989. Poslední maturity se konaly r. 1994 a později se již akreditaci maturitního studia nepodařilo obnovit. V září 1994 vzniklo vzdělávací středisko ve Stráži pod Ralskem, kde byly otevřeny 3 elokované třídy nástupního kurzu typu A pro 90 studentů a od roku 1995 se připravovalo k otevření další středisko v Kroměříži, kde na základě dohody s Justiční akademií vznikly nové prostory pro vzdělávání zaměstnanců VS ČR zprovozněné v roce 1996 (středisko bylo zrušeno 31. 7. 2006).
Od 1. 11. 1996 se sídlo Institutu přestěhovalo z Brna do Stráže pod Ralskem. Výstavbu nového sídla Institutu ve Stráži pod Ralskem zahájila akciová společnost METROSTAV na podzim roku 1998. Nová budova Institutu byla po ukončení stavebních prací slavnostně otevřena 31. 8. 2000. V období mezi rokem 2000 a 2015 prošlo všemi kurzy organizovanými v rámci Programu celoživotního vzdělávání pro zaměstnance Vězeňské služby ČR celkem 30 375 studentů.
Od 1. září 2013 dochází na základě schválené novely zákona č. 555/1992 Sb. ke změně názvu organizace, a to z Institutu vzdělávání VS ČR na Akademii Vězeňské služby.