הקבוצה נוסדה ב-1960 בעיר יוסטון, טקסס, תחת השם יוסטון אוילרס, והצטרפה לליגת ה-AFL שזה עתה נוסדה. היא העפילה בשלוש השנים הראשונות לגמר הליגה, וזכתה בו פעמיים רצופות ב-1960 ו-1961. ב-1968 הפכה טנסי לקבוצת הראשונה בפוטבול המקצועני, שמגרשה הביתי הוא באצטדיון מקורה, כשעברה לשחק באסטרודום ביוסטון. לאחר האיחוד בין ה-AFL וה-NFL ב-1970 עברה הקבוצה לשחק בבית המרכזי של חטיבת ה-AFC, אליו השתייכה עד לשנת 2002 עת עברה לבית הדרומי.
לאחר שעיריית יוסטון סירבה לממן בניית אצטדיון חדש, קיבל בעלי הקבוצה הבטחה מעיריית נאשוויל להשקעה באצטדיון חדש ולתגמולים נוספים, והוא העביר את הקבוצה לטנסי ב-1997. בשנתיים הראשונות לאחר המעבר שיחקה הקבוצה בממפיס מאחר שבניית האצטדיון טרם הושלמה, ונקראה טנסי אוילרס. שנים אלו אופיינו בנוכחות דלה של קהל, כיוון שהקבוצה לא הצליחה ליצור זיקה לממפיס או לנאשוויל. ב-1999 שונה שמה של הקבוצה לטנסי טייטאנס, והיא החלה לשחק במגרשה הביתי החדש שבנייתו הסתיימה. עונה זו הייתה שנת שיא בתולדות המועדון, הקבוצה השיגה מאזן של 13 ניצחונות לעומת 3 הפסדים בלבד, היא ניצחה במשחק הראשון בפלייאוף את באפלו בילס בזכות מהלך חריג, שזכה לכינוי Music City Miracle (בתרגום חופשי: הנס של עיר המוזיקה), ושני ניצחונות נוספים הובילו אותה למפגש בסופרבול מול סנט לואיס ראמס. המשחק הוכרע רק במהלך ההתקפה האחרון של טנסי, כששחקנה קן דייסון נעצר על קו השער על ידי מייק ג'ונס, שהבטיח את ניצחונם של הראמס 16–23. בעונות 2000, 2002, 2003, 2007, 2008, 2017, 2019 ו-2020 העפילה הקבוצה לפלייאוף, אך נכשלה בניסיונותיה להגיע לסופרבול.