המתיישבים הראשונים שהגיעו לאזור שנקרא היום "האי הגדול של ארץ האש", היו ציידים-לקטים שנדדו ברגל מהצפון, לפני כ־11,000 שנים, שהיו מוכנים לשרוד עם המשאבים הטבעיים שהציע השטח שהיה חלק מפטגוניה. קבוצות אלו היו קשורות לטוואלצ'ה (בספרדית: tehuelches). הכוונה לילידים שחיו באזור פטגוניה. הם בנו את הכפרים סלקנם ואווש (בספרדית: Selknam ו־Haush). מהאיים המערביים של פטגוניה הגיע גל נוסף של מתיישבים, נוודי הים מבני היאמנה והקוואסגר (בספרדית: yamanas ו־kawesgar).

ב־18 בינואר 1869, בהסכמתו של הממשל הארגנטינאי, התבסס מיסיון אנגליקני בראשו של ווייט הוקין סטרלינג (Waite Hockin Stirling), אשר הקים את ההתיישבות הראשונה שלא הייתה ילידית באזור, אשר הייתה עתידה להפוך לעיר. שנה לאחר מכן החליף אותו תומאס ברידג'ס (Thomas Bridges).

ב־1873 יזם נשיא ארגנטינה חוליו ארחנטינו רוקה תוכנית להקמת מושבת עונשין באושואיה, שמטרתה הייתה לשמור על ביטחון אזרחי ארגנטינה ובנוסף לחזק את הריבונות הארגנטינאית באזור, אך הדבר לא התאפשר עד הסכם הגבולות בין ארגנטינה לצ'ילה ב־1881. היום שנחשב ליום ייסודה של אושואיה כעיר הוא ה־12 באוקטובר 1884, היום בו אגוסטו לסרה, יצר את הנציבות הראשונה על חוף תעלת ביגל, כשהמיסיונרים וקצינים ימיים חתמו על הצו. דון פליס פס נבחר להיות מושל טיירה דל פואגן וב־1885 הוא הכריז על העיר כבירתה, אף על פי שהממשלה הפדרלית הארגנטינאית אישרה זאת רק ב־1904.

לא היה תיחום רחובות עד 1894 והכפר גדל והפך לכפר ציורי ססגוני. בתחילת המאה ה־20, נבנה בקרבת הכפר של אושואיה הכלא המפורסם שעבד בשנים 1902–1947. הכנסייה האנגליקנית הפסיקה את עבודתה והפעילויות היחידות בעיר מלבד ניצני מסחר, היו עובדי הממשלה והכלא. מאוחר יותר עבר לידיו של צבא ארגנטינה ולאחר זמן קצר ננטש, כיום במבנה זה נמצא המוזיאון הימי וכלא אושואיה. בין היתר בכלא עברה הרכבת הדרומית ביותר בעולם, שהובילה את האסירים מבית הכלא עד למחנות העבודה שהיו ממוקמים בשטח שכיום הוא חלק מהפארק הלאומי של ארץ האש. כיום הרכבת משמשת בעיקר למטרות תיירות.

מרגע הגעתו של האדם הלבן לאדמה זו, הילידים סבלו מאוד מהפרעות בחייהם. מאושואיה ועד נקודות אחרות יצאו כנופיות של שכירי חרב שנשכרו על ידי חוואים, בהסכמתן של הרשויות, להשמיד את אוכלוסיית הילידים, וכך עד שנת 1930 הם נעלמו כמעט לחלוטין.

המילה אושואיה מורכבת משתי מילים בשפת "ז'גן" (בספרדית: Yagan, שפת הנוודים באיים הדרומיים של צ'ילה וארגנטינה) אוש ('לעומק') והמילה וואיה (מפרץ/ערוץ), ותרגומה הוא "מפרץ עמוק" או "מפרץ תחתון". בספרדית מבטאים את שם העיר או־סו־איה.

בשנת 1971 ערכה העירייה תחרות לבחירת סמל העיר, ובה זכה המגן בעיצובו של ויסנטה גומס (Vicente Gomez).

המוטו של העיר הוא: "אושואיה, סוף העולם, ההתחלה של הכל" (בספרדית: "Ushuaia, fin del mundo, principio de todo").