La antigua Cárcel celular de Vitoria se crea en 1861 como cárcel de tercera clase en el extremo este de la capital, funcionando como cárcel correccional de partido y dependiente de la Diputación Foral. El edificio, de forma radial y con tres pisos, albergaba 72 celdas generales, tres para enfermería, dos salas destinadas a mujeres y otras dos a presos políticos, además de un local para escuela, un locutorio y cuatro patios. Su capacidad máxima era de 60 reclusos (a principios del XX aumentarán a 94) con una plantilla inicial de un Jefe, dos Ayudantes, tres vigilantes y un médico, que después se incrementará con un subjefe, dos nuevos vigilantes, un capellán y un demandadero. Para la custodia exterior existía guardia militar.

La cárcel celular de Vitoria va ser el primer centro penitenciario en llevar a la práctica las nuevas ideas de reforma carcelaria propuestas por filántropos e higienistas desde la segunda mitad del siglo XVIII: la cárcel celular, frente a las cárceles mazmorras medievales, parte del principio de aislamiento de los internos en celdas y propone la acción reformadora de los reclusos.

En 1930 se aprueba el Reglamento orgánico de los Servicios de Prisiones (R.D 21 de noviembre) que crea las Prisiones provinciales, enclavadas en las capitales de provincia para la permanencia de detenidos y procesados durante la tramitación del sumario y hasta que se celebre el juicio oral, y establece la estructura orgánica de los centros provinciales con las siguientes Oficinas:

-Dirección: para los asuntos del personal de prisiones, comunicaciones y documentos. Depende del Director del centro.

-Régimen: le compete todo lo referente a la población reclusa, incluidos los expedientes procesales y penales.

-Administración: para toda la contabilidad económica.

-Servicio interior: le corresponde cursar los partes reglamentarios del Director y dar cumplimiento a sus órdenes-

-Identificación: para el servicio de filiación e identidad dactiloscópica de los reclusos

Los servicios sanitarios y los de Instrucción y Educación estarán al cargo del personal facultativo correspondiente y no constituyen por tanto oficinas propias.

Este Reglamento será declarado vigente en 1936 (Decreto nº 83 del Gobierno del Estado) hasta la aprobación de un nuevo Reglamento en 1948 (Decreto de 5 de marzo del Ministerio de Justicia), finalmente sustituido en 1956 por el Reglamento de los Servicios de Prisiones (Decreto de 2 de febrero del Ministerio de Justicia). La legislación franquista va a mantener la estructura orgánica básica del Reglamento de 1930.

Durante la guerra civil y el franquismo, la Cárcel Provincial de Vitoria, ubicada en la calle de La Paz, se convertirá en símbolo de la represión de la dictadura hasta que, el 11 de Julio de 1973, los últimos presos fueran trasladados a la Colonia Penitenciaria de Nanclares de la Oca, antes Campo de Concentración (1940-1947) situado en esa localidad alavesa, a 15 Km de la capital. La cárcel será demolida en 1975.

Tres años después comenzará la edificación del actual Centro Penitenciario de Nanclares de la Oca, inaugurado en 1981 como centro de cumplimiento de penas, de acuerdo a la nueva clasificación establecida en la legislación (Ley General penitenciaria de 1979 y Reglamento de desarrollo); el único de esta categoría en la Comunidad Autónoma Vasca, ya que, tanto Martutene como Basauri son establecimientos de preventivos.

El centro penitenciario de Nanclares de la Oca depende de la Secretaría de Estado para la Seguridad del Ministerio de Interior, que lo gestiona a través de la Dirección General de Instituciones Penitenciarias (R.D 1181/2008, de 11 de julio, por el que se modifica y desarrolla la estructura orgánica básica del Ministerio de Interior).