Budova, v ktorej dnes sídli Museo Marítimo, je mimoriadne pochmúrnou atrakciou Ushuaie: tento veľký komplex bol totiž kedysi väzením. Postavili ho na začiatku 20. storočia, keď bola Ushuaia trestaneckou kolóniou. Do roku 1920 malo väzenie už päť blokov dokopy s 286 celami. V roku 1947 ho zavreli a odovzdali do rúk námorníctva, ktoré si tu v roku 1950 zriadilo námornú základňu.
Základňa bola od mesta prakticky izolovaná, až do pádu diktatúry v roku 1983. V bývalom väzení dnes sídli múzeum a celý komplex sa stal kľúčovou turistickou atrakciou (okrem plavieb do Antarktídy). Jedno z krídel väznice ostalo zachované v pôvodnom stave, zatiaľ čo vo zvyšných sídlia expozície múzea. Tie sa okrem námorníctva venujú aj samotnému väzeniu, Antarktíde a vojne o Falklandy, ktorá je tu známa ako Conflicto de las Islas Malvinas.
