Indijanci Selk’nam, imenovani tudi Ona, so prvič prispeli na Ognjeno zemljo pred približno 10.000 leti. Južna skupina avtohtonih prebivalcev tega območja, Jaghan (znana tudi kot Jámana), ki je zasedla današnjo Ushuaijo, je živela v stalnih konfliktih s severnimi prebivalci otoka.[1]

Skozi večino druge polovice 19. stoletja je bil vzhodni del Tierra del Fuego naseljena z veliko večino državljanov, ki niso bili argentinski državljani, vključno s številnimi Britanci. Britanski misijonarji so Ushuaio neformalno ustanovili po predhodnih britanskih raziskavah, še preden so argentinski državljani ali vladni predstavniki stalno prišli tja. Britanska ladja HMS ''Beagle'' je pod poveljstvom kapitana Roberta Fitzroyja prvič prispela do kanala 29. januarja 1833 med prvo plovbo po Tierra del Fuego. Mesto so prvotno poimenovali zgodnji britanski misijonarji[2] z uporabo domačega imena Yámana za to območje. Velik del zgodnje zgodovine mesta in njegovega zaledja je opisan v knjigi Lucasa Bridgesa Uttermost Part of the Earth (Skrajni del Zemlje) (1948). Ime Ushuaia se prvič pojavlja v pismih in poročilih Južnoameriškega misijonskega društva v Angliji. Britanski misijonar Waite Hockin Stirling je postal prvi Evropejec, ki je živel v Ushuaii, ko je med 18. januarjem in sredino septembra 1869 ostal z ljudstvom Yámana. Leta 1870 je prišlo več britanskih misijonarjev, da bi ustanovili majhno naselje. Naslednje leto je bil sklenjen prvi zakon. Leta 1872 je bilo registriranih 36 krstov in 7 porok ter prvo evropsko rojstvo (Thomas Despard Bridges) na Ognjeni zemlji.[3]

Leta 1871 je anglikanski pastor Thomas Bridges z družino kot prvi beli priseljenec na Ognjeni zemlji prispel s Falklandskih otokov in 30. septembra, po tem, ko se je predhodno strinjal z argentinsko suverenostjo, na kraju, kjer danes stoji letališče, postavil misijon in naselbino, ki jo je po jeziku staroselskega ljudstva Jaganov poimenoval Ushuaia (ush – zaliv, ki gleda na zahod – wuaia). Prva hiša, zgrajena v mestu Ushuaia, je bila vnaprej sestavljen 3-sobni dom, pripravljen na Falklandskih otokih leta 1870 za velečasnega Thomasa Bridgesa. Ena soba je bila namenjena družini Bridges, druga pa zakonskemu paru Yámana, tretja pa je služila kot kapelica.[4]

 

Zgradba vlade province v mestu Ushuaia s tipično lokalno arhitekturo.

Thomas Bridges se je naučil jezika Jaghanov (prebivalci obalnega morja) in ga tekoče govoril. V manjši meri je lahko komuniciral v jeziku Ona (prebivalci gozdov). Njegovo misijonarsko delo je bilo usmerjeno predvsem v Jagane. Beseda Jamana preprosto pomeni 'ljudje'. Napisal je slovar jezika Jaghan, katerega izvirni rokopis je v Britanskem muzeju. Ker Jagani niso imeli sposobnosti niti sredstev za pisanje, je moral Thomas Bridges zgraditi abecedo, ki je bila primerna za fonetiko jezika. Prvotni rokopis je bil trikrat izgubljen, vendar je bil obnovljen in skoraj objavljen z napačnim imenom. Pri upodabljanju tega slovarja je bila v preteklih letih uporabljena več kot ena abeceda. Odisejada rokopisa je zajela skoraj pol stoletja, preden je bil dokončno objavljen. Natalie Goodall je bila ključna pri ponatisu slovarja leta 1987 in dragocenem vpogledu v zgodovino dela Thomasa Bridgesa. Izvodi slovarja vsebujejo gradivo o uporabljenih črkah in izgovorjavah, ki se v mnogih pogledih razlikuje od abecede, ki se uporablja v angleškem jeziku. (Glej: A de la Rue).

Argentino je kmalu zaskrbelo zaradi povečane britanske prisotnosti na Ognjeni zemlji, zato je proti jugu poslala odpravo pod poveljstvom Augusta Laserra, ki je septembra 1884 prispela v Ushuaio in 12. oktobra istega leta z obešenjem argentinske zastave pred novozgrajenim oporiščem tudi formalno potrdila argentinsko suverenost. Ta datum velja za ustanovitev današnjega mesta.

Leta 1873 sta Juan in Clara Lawrence, prva argentinska državljana, ki sta obiskala Ushuaio, prispela poučevati v šolo. Istega leta je Julio Argentino Roca, ki je pozneje dvakrat služboval kot argentinski predsednik, spodbujal ustanovitev kazenske kolonije za prestopnike po vzoru tiste v Tasmaniji v Avstraliji, da bi zagotovil stalno prebivališče iz Argentine in pomagal vzpostaviti argentinsko suverenost nad celotno Ognjeno zemljo. Toda šele po pogodbi o meji iz leta 1881 med Čilom in Argentino so se začela formalna prizadevanja za ustanovitev občine in njenega zapora.

V 1880-ih je v Ushuaijo prišlo veliko iskalcev zlata po govoricah o velikih zlatih poljih, ki so se izkazale za napačne. 12. oktobra 1884 je v okviru južnoatlantske ekspedicije komodor Augusto Lasserre ustanovil pododdelek Ushuaia, misijonarji in mornariški častniki pa so podpisali Act of Ceremony. Don Feliz M. Paz je bil imenovan za guvernerja Tierra del Fuego in leta 1885 za glavno mesto imenoval Ushuaijo. Leta 1885 je bila teritorialna policija organizirana pod vodstvom Antonia A. Romera. Toda šele leta 1904 je zvezna vlada Argentine Ushuaio priznala kot glavno mesto Ognjene zemlje.

Ushuaia je utrpela več epidemij, vključno s tifusom, oslovskim kašljem in ošpicami, ki so precej zmanjšale domorodno prebivalstvo. Ker pa Jámana niso bili vključeni v popisne podatke, natančno izgubljene številke niso znane. Prvi popis je bil izveden leta 1893, v katerem je v Ushuai živelo 113 moških in 36 žensk. Zapor je leta 1896 uradno ustanovil izvršni ukaz takratnega vršilca dolžnosti predsednika Roce. Do leta 1911 so Jámani praktično izginili, zato je bil misijon zaprt.[5] Prebivalstvo se je do popisa leta 1914 povečalo na 1558.

Leta 1896 je zapor sprejel prve zapornike, v glavnem kršitelje in nevarne zapornike, premeščene iz Buenos Airesa, pa tudi nekatere politične zapornike. Ločen vojaški zapor je bil odprt leta 1903 v bližini Puerto Golondrina. Oba zapora sta se združila leta 1910 in ta kombinirani kompleks stoji še danes.[6] Tako se je v prvi polovici 20. stoletja mesto osredotočilo na zapor, ki ga je zgradila argentinska vlada, da bi povečala argentinsko prebivalstvo in zagotovila argentinsko suverenost nad Ognjeno zemljo. Zapor je bil po vzoru Britancev na Tasmaniji in Francozov na Hudičevem otoku namenjen ponavljalcem in hudim storilcem kaznivih dejanj. Pobeg iz Ognjene zemlje je bil prav tako težak, čeprav sta dva zapornika za nekaj tednov uspela pobegniti v okolico. Zaporniško prebivalstvo so tako postali prisilni kolonisti in so večino svojega časa gradili mesto z lesom iz gozda okoli zapora. Zgradili so tudi železnico do naselja[7], ki je danes turistična atrakcija, znana kot Vlak na koncu sveta (Tren del Fin del Mundo), najjužnejša železniška proga na svetu..

 

Hidroplan argentinske mornarice, eden prvih, ki je prispel v Ushuaia v tridesetih letih prejšnjega stoletja

Zapor je deloval do leta 1947, ko je Peronova vlada zapor odpravila in na njegovem mestu postavila mornariško oporišče, s katerim je izrazila svoje zahteve po Antarktiki. Večina stražarjev je ostala v Ushuaiji, medtem ko so bili ujetniki preseljeni v druge zapore severneje.

V 1970-ih so davčne olajšave privabile številne priseljence iz ostalih predelov Argentine in mesto je začelo doživljati skokovito rast prebivalstva.

Baza je do začetka 1990-ih delovala kot skladišče in pisarne. Kasneje je bila preurejena v sedanji muzej Maritimo de Ushuaia.[8]

Pomorska baza v Ushuaiji je bila aktivna med falklandsko vojno leta 1982. Argentinska križarka ARA General Belgrano, ki jo je nato potopila britanska flota, je odplula iz pristanišča Ushuaia, kjer je bilo februarja 1996 postavljeno spominsko obeležje.