Nazwa miasta pochodzi z lokalnego języka Indian Yámana, w którym znaczy zatoka u krańca (ush – w głębi, wuaia – zatoka). Właściwa wymowa nazwy miasta brzmi Usuaia. Indianie z grup Yámana, Alakaluf, Selk'nam oraz Manek'enk (Haush) zamieszkiwali te rejony od okołu 12 000 lat. Pierwsze stałe osiedle Europejczyków w rejonie Kanału Beagle założył w 1869 anglikański pastor Thomas Bridges.

Miasto Ushuaia oficjalnie założono 12 października 1884. Pod koniec XIX wieku władze Argentyny postanowiły uczynić z Ziemi Ognistej kolonię karną (podobnie jak Imperium Brytyjskie poczyniło z Australią). Odległa, dzika wyspa miała uniemożliwić więźniom wszelkie ucieczki. Do budowy więzienia przystąpiono w Ushuaia w 1902; prace nad nim trwały do 1920 i były prowadzone wyłącznie za pomocą rąk skazańców. Więźniowie pracując na miejscu w różnorakich zawodach zapewniali Ushuaia samowystarczalność a wokół więzienia zaczęło wyrastać miasteczko.

W 1947 dzięki polityce demokratyzacji państwa prowadzonej przez Juana Peróna więzienie zostało zamknięte. Dziś w jego murach istnieje popularne muzeum. Inną pozostałością tamtych czasów jest zabytkowa kolejka Tren del Fin del Mundo. Transportowała ona niegdyś pozyskiwane przez więźniów drewno z okolic obecnego Parku Narodowego Ziemi Ognistej.

Olbrzymi wkład w rozwój miasta wniósł włoski przedsiębiorca Carlo Borsari sprowadzając do miasta swoich rodaków z biednych powojennych Włoch. Pierwszy statek z imigrantami i materiałami budowlanymi przypłynął z Genui w październiku 1948, następny we wrześniu 1949.