Перші люди у цій місцевості з'явилися близько 11 тисяч років тому. Довгий час тут жили племена індіанців ямана, она, ауш, алакалуфів.

18 січня 1869 року в бухті Ушуая була заснована англіканська місія.

28 вересня 1884 року до поселення британців прибули три сотні аргентинців. Офіційною датою заснування міста вважається 12 жовтня 1884 року, коли Аугусто Лассерре створив субпрефектуру на берегах протоки Бігля з метою підтвердити належність цих земель до Аргентини. Місцеві індіанці і місіонери підписали акт заснування міста.

Назва Ушуая походить з яганської мови і складається з двох частин: ush (на дні) і waia (бухта), що разом означають «глибока бухта». У акті заснування міста назва писалася як Oshovia[1].

25 листопада 1884 року було обрано першого губернатора території Вогняна Земля.

Після приходу білих людей життя корінних мешканців Ушуаї різко змінилося на гірше, і до 1930-х років майже всі місцеві індіанці були винищені.

Рання історія міста детально описана в книзі Лукаса Бріджеса «На самому краю Землі» (англ. Uttermost Part of the Earth, 1948). Між 1902 і 1947 роками місто було невеликим поселенням біля колонії для небезпечних злочинців. Аргентинський уряд створив цю колонію за прикладом Британії, яка відсилала в'язнів до Австралії або Франції, що відсилала їх до Острова Диявола (фр. Île du Diable): втекти з в'язниці на віддаленому острові було неможливо. В'язні, таким чином, ставали примусовими колоністами, та витрачали час на будівництво свого поселення. Одним із найвідоміших в'язнів цієї колонії був український анархіст Симон Радовицький. Також тут була споруджена найпівденніша залізниця у світі, яка проходила від в'язниці до робочих таборів довжиною 7 км. Зараз вона розташована у межах національного парку Вогняна Земля і є туристичною пам'яткою під назвою «Поїзд Кінця Світу» (ісп. Tren del Fin del Mundo). Старовинна в'язниця перетворена на музей.

1950 року в Ушуаї було засновано базу ВМС Аргентини.

Зараз Ушуая є важливим туристичним центром Аргентини, де є гірськолижні і альпіністські курорти, а також Національний парк.