En el año 1883 el presidente Roca presentó en el senado un proyecto de "Colonia penal al sur de la república" con la intención de resolver el problema penitenciario y asegurar la soberanía, aunque su idea no fue llevada a cabo. Bajo la presidencia de Luis Saenz Peña, se retoma la idea de una cárcel en Tierra del Fuego pero para el cumplimiento de la pena de reincidencia, esto fue debido al gran crecimiento del delito en la Capital Federal. En el año 1895 se promulga la ley N°3335 que pide el cumplimiento de penas correccionales o de presión para reincidentes por segunda vez, estas penas tenían que cumplirse en los territorios nacionales al sur, el poder ejecutivo debía designar qué lugar. Finalmente deciden que Ushuaia sea el lugar para el cumplimiento de estas penas y fue creado el presidio por decreto en el año 1896. En enero de ese año parte la primer remesa de presos, 14 hombres voluntarios, semanas después parte la segunda remesa en la que se incluyeron 10 mujeres también voluntarias, la idea era formar una colonia penal.
La construcción del Presidio y Cárcel de Reincidentes comenzó el 15 de septiembre del año 1902, culminando en 1920. La mano de obra fueron los mismos penados. La prisión contaba con varios talleres de oficios: panadería, carpintería, herrería y más, además tenían farmacia, servicio médico, teléfono y una usina. Los servicios eran extensivos para la ciudad de Ushuaia, lo que hacía que los pobladores pudieran comprar pan o muebles hechos por los penados. Hubieron varios presos renombrados, como Simón Radowitzky, Cayetano Santos Godino, entre otros. La prisión fue cerrada por decreto el 21 de marzo del año 1947 bajo la presidencia de Juan Domingo Perón. Las instalaciones fueron cedidas a la armada para que pusiera una base naval.