למרות חששות ה-NHL, הקבוצה צברה במהירות פופולריות בדאלאס, הן עקב המגמה של התפשטות הפופולריות של הענף דרומה והן עקב ההצלחה המיידית של הקבוצה ועונה מצוינת שרשם מייק מודנו. כבר בעונת 1994, הראשונה בדאלאס, רשמה הקבוצה שיאי מועדון של 42 ניצחונות ו-97 נקודות בטבלה ועברה סיבוב פלייאוף מול סנט לואיס בלוז. בסיבוב השני נוצחה על ידי ונקובר קנאקס.
עונת 1995 החלה באיחור בשל סכסוך עבודה בליגה שהוביל להשבתת מגן מצד בעלי הקבוצות. בזמן ההשבתה מכר נורמן גרין את הקבוצה לאיש העסקים המקומי טום היקס. העונה החלה עם שתי עסקאות גדולות בהן הועברו מהקבוצה הקפטן שלה, מייק טינורדי, והחלוץ הוותיק ניל ברוטן. בעסקת טינורדי קיבלו הסטארס את החלוץ קווין האצ'ר, שהצטרף בקבוצה לאחיו, דריאן, מגן שהגיע שנה קודם לכן. דריאן האצ'ר מונה לקפטן במקומו של טינורדי. העונה המקוצרת הייתה רעה לסטארס, שעלו בקושי לפלייאוף עם מאזן שלילי ונוצחו בסיבוב הראשון.
בעונת 1996 החמיצו הסטארס את הפלייאוף לראשונה מאז המעבר לדאלאס, אולם יצאו מהעונה עם רכש משמעותי - החלוץ המרכזי ג'ו ניוונדייק שהגיע מקלגרי פליימס. תמורתו ויתרו הסטארס על שחקן צעיר שלא נחשב לכוכב בהתהוות, אולם בסופו של דבר התברר ככזה, ג'רום איגינלה.
החיזוק נמשך בעונת 1997 עם רכש של שני מגינים מהטובים בליגה - סרגיי זובוב ודריל סידור. עם מאמן חדש, קן היצ'קוק בעונתו הראשונה ב-NHL, סיימו הסטארס ראשונים בבית המרכזי ועלו לפלייאוף כמדורגים 2 במערב. בפלייאוף הופתעה הקבוצה על ידי אדמונטון אוילרס כבר בסיבוב הראשון.
לקראת עונת 1998 המשיכה הקבוצה להתחזק, והפעם בעמדת השוער - אד בלפור, שכבר נחשב לכוכב בליגה, הגיע כשחקן חופשי. הסטארס סיימו את העונה הרגילה במאזן הטוב ביותר בליגה בפעם הראשונה בתולדות הקבוצה, אולם בסיבוב השני של הפלייאוף - ללא ג'ו ניוונדייק הפצוע - כשלו מול האלופה, דטרויט רד וינגס.
ריצת הפלייאוף של 1999: אליפות היסטורית.
עונה לאחר מכן זכו הסטארס לעוד חיזוק משמעותי בדמות החלוץ ברט האל. האל, בנו של כוכב שנות ה-60 בובי האל, היה חלוץ פורה ביותר שסיים שלוש עונות רצופות עם למעלה מ-70 שערים בסנט לואיס בלוז. הסטארס שלטו בליגה מתחילתה ועד סופה, סיימו את העונה הרגילה עם 51 ניצחונות ו-114 נקודות - שני שיאי מועדון - ועלו לפלייאוף בקלות. בפלייאוף הדיחו את אדמונטון אוילרס ואת סנט לואיס בלוז, ועלו לגמר החטיבתי מול קולורדו אוולאנש. הסטארס הפכו פיגור של 3:2 בסדרה וניצחו אותה ב-7 משחקים, ובכך עלו לסדרת גמר גביע סטנלי לראשונה מאז המעבר לדאלאס, שם פגשו את אלופת המזרח באפלו סייברס. עם ניצחון 4:2 בסדרה, זכו הסטארס בגביע סטנלי בפעם הראשונה, כולל תקופת מינסוטה.
2000 - 2019.
בעונת 2000 המשיכו הסטארס להרשים והיו קרובים להגן על תוארם כשהגיעו בפעם השנייה ברציפות לסדרת גמר גביע סטנלי, אולם הפעם נוצחו על ידי ניו ג'רזי דווילס.
ב-2001 עזבו הסטארס את אולמם הישן, "ריוניון ארנה", ועברו לאולם חדש, אמריקן איירליינס סנטר.
בארבע העונות שלפני עונת 2005 שבוטלה בשל סכסוך עבודה ב-NHL הגיעו הסטארס לפלייאוף עוד שלוש פעמים, אולם נוצחו בסיבובים המוקדמים. אחרי העונה המבוטלת, עונת השיא של הסטארס בעשור הראשון של המאה ה-21 הייתה עונת 2008, בה הגיעו לגמר החטיבה המערבית כאשר הם מדיחים בדרך את האלופה היוצאת, אנהיים דאקס. בגמר החטיבתי נוצחו הסטארס על ידי דטרויט רד וינגס.
ב-2009 ו-2010 לא הצליחו הסטארס להגיע לפלייאוף. בסיום העונה שוחרר מהקבוצה הכוכב הוותיק מייק מודנו, שעבר לדטרויט רד וינגס, והשוער מרטי טרקו שעבר לשיקגו בלאקהוקס.
בעונת 2011 נאבקו הסטארס על המקום בפלייאוף, כאשר לקראת סיום העונה התמקד המאבק על הכרטיס האחרון לפלייאוף מהחטיבה המערבית בינם לבין האלופה היוצאת שיקגו בלאקהוקס. הפסד מול מינסוטה ויילד במשחק האחרון של העונה, משחק שניצחון בו היה מעלה את הסטארס לפלייאוף, עלה להם בהחמצת הפלייאוף זו עונה שלישית ברציפות.
בתחילת עונת 2012 הוכרזה הקבוצה כפושטת רגל, וה-NHL נטלה את הניהול בה. במכרז שיצא למכירתה של הקבוצה לבעלים חדשים הוגשה הצעה אחת בלבד, של איש העסקים הקנדי טום גליארדי, בעל רשת ענפה של מסעדות ומלונות. הרכישה אושרה על ידי ה-NHL ועל ידי בית המשפט שטיפל בתיק פשיטת הרגל של הקבוצה. עם זאת, גם בעונת 2012 המשיכה הקבוצה לצבור הפסדים כבדים.
מבחינה מקצועית חזר על עצמו סיפור העונה הקודמת כמעט במדויק - הסטארס היו במירוץ הפלייאוף עד השלבים הסופיים של העונה, והחמיצו אותו במשחקים האחרונים.
לעונה המקוצרת של 2012/13 התייצבה הקבוצה עם רכש נוצץ - החלוץ הצ'כי הוותיק יארומיר יאגר, אחד המבקיעים הגדולים בתולדות הליגה. הקבוצה גילתה חוסר יציבות, ונאבקה כדי לשרוד במאבק הפלייאוף. במהלך העונה, בסדרה של מהלכים תמוהים, ויתרה הקבוצה על כמה משחקניה המרכזיים - הקפטן ברנדן מורו, החלוץ המצטיין מייקל ריידר, ולבסוף הועבר מהקבוצה גם יארומיר יאגר, למרות שהצטיין במהלך העונה. למרות זאת, הקבוצה המשיכה להיאבק על מקום בפלייאוף עד המשחקים האחרונים של העונה, אולם לבסוף נכשלה שוב וסיימה עשירית בלבד בחטיבה המערבית. חמש העונות הרצופות בהן החמיצה הקבוצה את הפלייאוף הן שיא שלילי של המועדון, כולל ימי מינסוטה.
בעונת 2013/14 נאבקה שוב הקבוצה על מקום בפלייאוף, והפעם הצליחה להשתחל אליו לקראת סיום העונה ולשבור את רצף השנים ללא פלייאוף. בפלייאוף עצמו נוצחו הסטארס על ידי אנהיים דאקס והודחו בסיבוב הראשון. עונה אחת לאחר מכן חזרה הקבוצה ונכשלה במאבק ההגעה לפלייאוף.
עונה רגילה מצוינת ב-2015/16 הביאו לסטארס את אליפות הבית המרכזי, אך הסטארס הודחו בסיבוב השני בפלייאוף לאחר הפסד ביתי במשחק שביעי ומכריע מול סנט לואיס בלוז. חוסר היציבות נמשך בשתי העונות הבאות והקבוצה שוב סיימה הרחק מהמקומות המובילים לפלייאוף.
הסטארס שבו לפלייאוף ב-2018/19 מהמקום השביעי במערב, ואף הפתיעו בסיבוב הראשון את אלופת הבית המרכזי נאשוויל פרדטורס בטרם גררו את סדרת הסיבוב השני נגד סנט לואיס בלוז, גם היא נגד יתרון הביתיות, למשחק שביעי ומכריע, בו נוצחו והודחו.
ריצת הפלייאוף של 2020.
לקראת עונת 2019/20, בניסיון לחזק את הקבוצה בשחקנים מוכחים ומנוסים, החתימה הקבוצה שני שחקנים ותיקים שהיו מנהיגים בקבוצותיהם הקודמות והגיעו איתן לשלבים המתקדמים - ג'ו פבלסקי, קפטן סן חוזה שארקס ששיחק בה 14 עונות והגיע איתה לסדרת הגמר על גביע סטנלי עונה אחת קודם לכן; וקורי פרי, שהגיע אחרי 14 עונות באנהיים דאקס איתה זכה בגביע סטנלי היחיד שלה ב-2007, ובמדיה היה ה-MVP של הליגה ב-2011 וזכה בגביע הארט.
הקבוצה הראתה במהלך העונה בעיקר משחק הגנה משובח בראשותו של השוער בן בישופ. למרות יכולת התקפית בינונית, היכולת ההגנתית הספיקה למקום שלישי בבית המרכזי ורביעי בחיטבה המערבית כאשר העונה נקטעה לקראת סיומה בשל מגפת הקורונה ויצאה לפגרה כפויה של כחמישה חודשים.
כאחת מארבע המדורגות ראשונות בחטיבה המערבית, השתתפה הקבוצה בבית מוקדם בשיטת ליגה עם שלוש המדורגות האחרות בראש החטיבה כחלק מפורמט הפלייאוף המיוחד באותה עונה. הסטארס נוצחו בשני משחקים וניצחו אחד, והשיגו את המקום השלישי בחטיבה לקראת הסיבוב הראשון של הפלייאוף. השוער בן בישופ נפצע במשחק הראשון, ואת מקומו תפס המחליף הרוסי אנטון חודובין. גם החלוץ המצטיין טיילר סגין נפצע ונעדר מהמשחקים הראשונים של הפלייאוף.
למרות הפציעות, בפלייאוף שיפרו הסטארס באופן משמעותי את יכולתם תוך שהם מפגינים משחק קבוצתי מתואם ושחקנים רבים שהעלו את רמתם. השוער המחליף חודובין נכנס לנעליו של בישופ והפגין את יכולתו בשער, חלוץ הרכש ג'ו פבלסקי והקפטן ג'יימי בן התעלו במשחק ההתקפה, והמגינים מירו הייסקאנן וג'ון קלינגברג הצטיינו משני צידי הזירה. הסטארס ניצחו את קלגרי פליימס בשישה משחקים ועלו לסיבוב השני מול קולורדו אוולאנש, שגם היא הפגינה יכולת משובחת בסיבוב הראשון.
הסדרה בין שתי הקבוצות הצדיקה את הציפיות ועלתה לרמה גבוהה מאוד מצד שתי הקבוצות. בהתאם, היא הגיעה למשחק שביעי ומכריע שהסתיים בדרמה גדולה, כשהחלוץ הפיני יואל קיווירנטה השווה את התוצאה ל-4:4 לקראת סיום הזמן החוקי, ובהארכה כבש שער נוסף והעלה את הסטארס לסדרת הגמר החטיבתי.
הגמר החטיבתי זימן לסטארס סדרה קשה נוספת מול וגאס גולדן נייטס. בעזרת יכולת גבוהה של חודובין בשער ושל מצטייני הסדרות הקודמות הצליחו הסטארס להתגבר על הגולדן נייטס בחמישה משחקים ששניים מהם הגיעו להארכה, ולעלות לסדרת הגמר על גביע סטנלי לראשונה זה 20 שנה.
בסדרת הגמר, מול טמפה ביי לייטנינג, ניצחו הסטארס במשחק הראשון, אך לאחר מכן נקלעו לסדרה של הפסדים ולפיגור בסדרה ממנו לא התאוששו, ונוצחו בסדרה בשישה משחקים.
2020 - ההווה.
במסגרת ארגון זמני מחדש של בתי הליגה בשל מגפת הקורונה, שובצו הסטארס לבית המרכזי, במסגרתו נאבקה הקבוצה על עלייה לפלייאוף וכשלה במשחקים האחרונים.
סגל שחקנים.
נכון ל-15 במאי 2022
חג החגים
יהודיה (עבאסיה)
ילנה שושונובה
ילנה לבובנה שושונובה (ברוסית: Елена Львовна Шушунова; מכונה לפעמים הלנה שושנובה; 23 באפריל 1969 – 16 באוגוסט 2018) הייתה מתעמלת סובייטית-יהודייה, אלופה אולימפית בעלת 4 מדליות מהן 2 זהב כולל החשובה מכולן בתחרות הקרב רב אישי, אלופת עולם בעלת 11 מדליות מהן 5 זהב ואלופת אירופה בעלת 7 מדליות מהן 5 זהב.