Ensimmäinen kausi NHL-kaupunkina toi ihmeitä kerrakseen Dallasin asukkaille. Teksasilaiset olivat tottuneet lähinnä seuraamaan maan ensisijaisia joukkueurheilulajeja; baseballia, koripalloa ja varsinkin amerikkalaista jalkapalloa, jossa Dallas Cowboys oli kaupungin ykköspuheenaihe. Jääkiekko oli vain murto-osalle kaupunkilaisista täysin tuttu urheilulaji.
Starsin otteluita saavuttiin katsomaan silti varsin aktiivisesti. Taitokiekkoa tuolloin ei kuitenkaan vielä osattu arvostaa. Tappelut, joita tuohon aikaan NHL:ssä oli huomattavasti enemmän kuin nykyään, saavuttivat suuren suosion uusien jääkiekkofanien keskuudessa. Dallas Starsin tulokaskaudella Reunion Arenan kaukalossa tapeltiinkin enemmän kuin koskaan sen jälkeen; teksasilainen punaniskayleisö rakasti rehtiä mies miestä vastaan -taistelua. Fanien ykkössuosikiksi nousikin kovanyrkkinen Shane Churla, joka keräsi Dallasin paidassa tuolla kaudella hurjat 333 jähyminuuttia.
Ensimmäisellä kaudella 1993-94 joukkueen valmennuksesta, kuten myös manageroinnista, vastasi Bob Gainey, joka oli usealle pelaajalle tuttu myös aiemmilta North Stars -kausilta. Pelaajisto ei kaupungin vaihtumisesta huolimatta muuttunut paljoakaan. Dallasin kantavina voimina hyökkäyspäässä häärivät kokeneet Dave Gagner, Russ Courtnall sekä Neal Broten.
Nuorta tulivoimaa tuli Ulf Dahlenilta ja ennen kaikkea joukkueen suurimmalta tähdeltä, Minnesotan vuoden 1988 ykkösvaraukselta, Mike Modanolta, joka iski tuolla kaudella 50 maalia. Kaudella 1993-94 Dallasin sotisovassa nähtiin myös Prahan MM-kisojen maalikuningas Jarkko Varvio. Tulokaskaudellaan suomalainen pelasi kuitenkin vain kahdeksan ottelua ylhäällä tehden kuitenkin kohtalaisen mukavat pisteet 2+3. Loppukausi sujui silloisessa farmijoukkueessa: IHL:n Kalamazoossa.
Ensimmäinen kausi Dallas Starsilla sujui pelillisesti erinomaisesti. Joukkue sijoittui kolmanneksi Läntisessä konferenssissa ja pudotti pudotuspelien ensimmäisellä kierroksella St.Louisin. Toisella kierroksella tuli seinä vastaan. Vancouver jyräsi fyysisyydellään Dallasin selvästi tieltään. Kovaluisen kapteeni Mark Tinordin loukkaantuminen oli lähes kuolinisku Starsin haaveille edetä pidemmälle pudotuspeleissä. Viihteellisen kiekon, tappeluiden ja hyvän menestyksen ansiosta Stars oli kuitenkin tulokaskaudellaan pelannut itsensä Dallasin urheilufanien tietoisuuteen.
Työsulun varjostama kausi 1994-95 oli Dallasin osalta loukkaantumisten värittämä. Mike Modano pelasi vammansa vuoksi vain 30 ottelua ollen silti joukkueen sisäisen pistepörssin toinen heti kokeneen kahden suunnan hyökkääjän Dave Gagnerin jälkeen. Joukkueeseen tuli kesken kauden melko suuria muutoksia. Avainpelaajat Neal Broten sekä Russ Courtnall kaupattiin muihin seuroihin ja tilalle tulivat Mike Donelly, Corey Millen ja Greg Adams, joka myöhemmin osoittautui oivaksi laituriksi Mike Modanon rinnalle.
Valmentaja/GM Bob Gainey sai ongelmista huolimatta luotsattua Starsin pisteen turvin pudotuspeleihin, mutta konferenssin kärkijoukkue Detroit oli aivan liian vahva Dallasille ja sarja olikin ohi jo viidessä pelissä. Kaudella 1994-95 Stars-faneille esiteltiin nuoret tulokkaat: Todd Harvey, Grant Marshall sekä Jamie Langenbrunner, joista myöhemmin tuli Dallasin vahvoja runkopelaajia.
Hitchcock ottaa ohjat ja menestyksen siemen kylvetään
Jo pitkään samaa joukkuetta valmentaneen Bob Gaineyn aika alkoi olla auttamatta ohi kauden 1995-96 keskivaiheilla. Dallas kulki tappiosta toiseen ja tyypilliseen NHL-tyyliin valmentaja sai lähteä. Gaineyn vika tuo huono menestys ei välttämättä ollut, sillä Starsin pelaajamateriaali ei todellakaan ollut kuin korkeintaan liigan keskikastia Mike Modanon ollessa joukkueensa ainoa tähti. Gaineyn tilalle otettiin farmijoukkue Kalamazoosta valmentaja Ken Hitchcock, joka aiemmin oli myös toiminut Philadelphian kakkosvalmentajana.
Hitchcock tunnettiin jo tuolloin varsin puolustusvoittoisen pelityylin ystävänä ja tuo muutos oli nyt myös luvassa Dallas Starsin joukkueessa. Pelit hieman paranivatkin kauden puolivälissä tapahtuneen valmentajan vaihdoksen jälkeen, mutta mitään ei ollut enää tehtävissä kauden pelastamiseksi. Dallas Stars jäi ensimmäisen kerran pudotuspelien ulkopuolelle.
Jotain positiivistakin kuitenkin tapahtui, sillä joukkueeseen liittyi kesken kauden huippusentteri Calgarystä, Joe Nieuwendyk. Stars tarvitsi kakkoskenttäänsä laatua ja Nieuwendyk veikin nyt Modanolta hieman huomiota vastustajien silmissä. Toinen tulevaisuuden kannalta erinomainen hankinta tuolla kaudella oli Guy Carbonneau, puolustavien senttereiden elävä legenda ja kaksinkertainen Stanley Cup voittaja. Tulokaskauttaan pelannut Jere Lehtinen sai Carbonneausta erinomaisen roolimallin.
Hitchcockin tulon myötä Starsista tuli hiljalleen tiivis ryhmä. jonka kaikkea tekemistä kuvasti kurinalaisuus. Kaudella 1996-97 ottelu toisensa jälkeen kääntyi Dallasin voitoksi, vaikka maaleilla ei joukkue mässäillytkään. Uuden toimivan systeemin ansiosta Stars tulikin Hitchcockin ensimmäisellä täydellä kaudella heti Läntisen konferenssin toiseksi.
Puolustus toimi nyt aivan erilailla kuin Gaineyn aikoihin. Mike Modano muodosti Jere Lehtisen ja Greg Adamsin kanssa toimivan ykkösnyrkin, mutta nyt Dallasilla oli ensimmäistä kertaa mahdollista tarjota faneilleen myös kunnon kakkoskenttä, joka pystyi ratkaisemaan otteluita. Joe Nieuwendyk teki ensimmäisellä täydellä kaudellaan tähtipaidassa 30 maalia vain 66 ottelussa. Jere Lehtisen huimaa työmoraalia alettiin arvostaa ympäri liigan ja kausi 1996-97 olikin suomalaisen läpimurto maailman kovimpaan kiekkoliigaan. Lehtisen lisäksi muut nuoret, kuten Jamie Langenbrunner sekä Bobby Orriinkin verrattu Darryl Sydor, löivät itsensä läpi.
Keväällä 1997 Dallasin pudotuspelit päättyivät joukkueen suureksi pettymykseksi jo ensimmäisellä kierroksella Edmontonia vastaan. Todd Marchant iski seitsemännen pelin jatkoajalla puolittaisesta läpiajosta Dallasin laulukuoroon. Tuosta huolimatta teksasilaisten tekemisessä oli nyt jotain aivan uutta ja kunnianhimoista. Paukkuja oli selvästi pidemmällekin.
Kaudella 1997-98 Dallas Starsista tuli NHL:n todellinen huippujoukkue. Sen osoitti Läntisen konferenssin voitto. Dallasin runkosarjamenestyksen tärkeä avain oli ehdottomasti uusi All-Star -maalivahti Ed Belfour. ”Eddie the Eagle” toi uskottavuutta Starsin tolppien väliin. Tämän lisäksi joukkueen puolustuspäähän oli muodostunut todella toimiva nelikko; joukkueen kapteeni Derian Hatcher, Richard Matvichuk, Sydor ja Sergei Zubov.
Kokeneet puolustavat sentterit Guy Carbonneau sekä Brian Skrudland varmistivat lopullisesti, ettei Dallasin päähän maaleja juuri tehty. Samaan aikaan tutuissa koostumuksissa olleet hyökkäysketjut (Adams-Modano-Lehtinen, Verbeek-Nieuwendyk-Langenbrunner) toimivat erinomaisesti. Näiden pohjalta Dallas eteni tuolla 1997-98 kaudella ensimmäistä kertaa historiassaan Läntisen konferenssin finaaliin asti, jossa tuleva mestari Detroit kuitenkin osoittautui vielä vahvemmaksi.
Joe Nieuwendykin loukkaantuminen pudotuspelien ensimmäisellä kierroksella San Josea vastaan oli kohtalokasta Starsille Stanley Cupin voittoa ajatellen. Miehen teloneen Bryan Marchmentin päätä vaadittiin vadille Teksasissa. Joka tapauksessa kausi 1997-98 antoi viitteitä tulevasta; enää Dallasissa ei tyydytty hyvään runkosarjaan vaan haluttiin voittaa mestaruus. Jere Lehtinen toi Starsin kannattajille ilon aihetta voittamalla ensimmäisenä suomalaisena Selke Trophyn, joka jaetaan kauden päätteeksi liigan parhaalle puolustavalle hyökkääjälle.
Kesällä 1998 edelleen GM:na toiminut Bob Gainey päätti tehdä kaikkensa Stanley Cupin tuomiseksi Dallasiin. Hän osti St. Louisista 554 maalin miehen tuomaan tehoja hyökkäykseen: amerikkalainen Brett Hull saapui Teksasiin. Samalla kun Dallasissa jatkoivat vanhat hyökkäyspään kärkinimet, puolustus oli liigan paras ja maalivahti loistava, voitiin olettaa, että mahdollisuudet olisivat mihin vain.
Odotukset lunastettiin ja Dallas oli runkosarjassa ylivoimainen voittaen Läntisen konferenssin peräti 16 pisteellä. Hull-Modano-Lehtinen oli täydellisesti roolitettu ketju ja sitä voidaan kutsua Starsin historian parhaaksi hyökkäyskentäksi. Miehet takoivat runkosarjassa yhteensä 191 pistettä, vaikka jokainen kärsikin pienistä loukkaantumisista.
Pudotuspeleissä Dallas kaatoi ensimmäisellä kierroksella Edmontonin suoraan neljässä pelissä. Toisella kierroksella vastaan luisteli St. Louis, joka oli jo kovempi vastus. Hull, Modano, Nieuwendyk sekä Zubov vastasivat kuitenkin voittomaaleillaan Starsin ottelusarjavoitosta numeroin 4-2. Konferenssin finaaliin asettui vastaa Peter Forsbergin sekä Joe Sakicin tähdittämä Colorado. Sarja olikin odotetun tiukka ja tarvittiin seitsemän peliä ratkaisemaan Stanley Cup -finalisti. Stars hoiti homman kotikaukalossa Mike Keanen maaleilla ja edessä oli ensimmäiset finaalit Dallasin historiassa. Jälkeenpäin Coloradon Joe Sakic sanoi Starsista: ”He ovat NHL:n kovin joukkue pitämään johtoasemansa. Nimet kuten Carbonneau, Lehtinen, Keane ja koko puolustus takaavat sen”. Tämä oli varsin totta.
Finaaleissa asettui vastaan Itäisen konferenssin yllätysjoukkue Buffalo Sabres, jonka maalilla pelasi koko liigan ehkä paras maalivahti: Dominik Hasek. Sarjasta oli odotettavissa kahden erinomaisesti puolustavan joukkueen taisto. Sabresin Mike Pecan tehtävänä oli varjostaa Modanoa ja aina kun se oli mahdollista. Buffalon valmentaja Lindy Ruff asetti Pecan samaan aikaan jäälle Dallasin ykköstähden kanssa. Buffalon kapteeni oli aiemmin onnistunut tehtävässään muun muassa Toronton Mats Sundinia vastaan.
Ensimmäinen ottelu pelattiin Dallasin Reunion Arenalla. Buffalon puolustaja Jason Woolley hiljensi jatkoajalla teksasilaiset tekemällä voittomaalin Belfourin selän taakse. Toiseen peliin saapui vihainen ja hyvin latautunut Stars, joka veikin ottelun nimiinsä numeroin 4-2. Tämän jälkeen oli aika siirtyä Buffaloon, jossa pelattiin kaksi vähämaalista ja tiukkaa ottelua. Molemmat joukkueet voittivat jälleen kerran, samoin numeroin 2-1.
Ottelusarja pysyi jännittävänä: voitot tasan 2-2 ja takaisin Dallasiin. Siellä kotijoukkue otti henkisesti tärkeän voiton Sydorin ja Verbeekin maaleilla numeroin 2-0. Ottelun lopussa, summerin jo soitua nähtiin episodi, jossa Buffalon Rhett Warrener paini Dallasin Derian Hatcherin kanssa Stars-maalilla. Tuloksena oli Warrenerin katkennut jalka ja miehen kausi oli ohitse - Hatcher otti fyysisyydellään henkisen yliotteen Buffalon joukkueesta.
Kuudes ottelu pelattiin Buffalossa ja sen tapahtumat jäävät ikuisesti NHL:n historiankirjoihin. Ensimmäisessä erässä Jere Lehtinen yllätti pienestä kulmasta Dominik Hasekin ja Stars meni johtoon 1-0. Toisen erän lopulla Stu Barnes räjäytti Sabresin tuvan täyden yleisön huutoon, napauttamalla tarkan rannevedon ohi Belfourin tasoittaen numerot 1-1. Kolmas erä ei muuttanut tilannetta vaan lähdettiin hermojaraastavalle jatkoajalle.
Jatkoerässä Brett Hull iski legendaarisen ja ikuisesti kyseenalaisen maalin Lehtisen syötöstä. Hullin luistin oli hieman maalivahdin alueella, mutta tuomari hyväksyi maalin ja Dallasin mestaruusjuhlat saattoivat alkaa. Suuret pelaajat Mike Modano, Brett Hull ja Ed Belfour saivat täten uransa ensimmäiset Stanley Cup -mestaruussormukset ja juhlat olivat sen mukaiset.
Bob Gaineyn hankinnat olivat osoittautuneet oikeiksi ja koko Dallasin kaupunki juhli seuraavan viikon. Joe Nieuwendyk, joka teki peräti kuusi voittomaalia pudotuspeleissä, palkittiin ansaitusti Conn Smythe -palkinnolla. Valmentaja Ken Hitchcock sanoi: ”Ed Belfour ja Joe olivat meidän parhaat pelaajat pudotuspeleissä, mutta Mike Modano oli paras viimeisessä kahdessa ottelussa”. Jere Lehtinen voitti toisena vuonna peräkkäin Selke Trophyn.
Dallas Stars jäi siis edellisen vuosituhannen viimeiseksi mestariksi NHL:ssä. Joukkueen nouseva trendi koko 1990-luvun johti mestaruuteen. Satsaukset (Hull, Belfour, Nieuwendyk) olivat kalliita, mutta kannattavia. Seuraavalla kaudella Stars pääsi vielä Stanley Cup -finaaleihin, mutta New Jerseystä leivottiin mestari. Devilsin Jason Arnott sai kunnian tehdä kannun ratkaisseen, mutta myös Reunion Arenan viimeisen maalin, sillä Dallasiin oli rakenteilla uusi areena, American Airlines Center.
2000-luvulla Starsin pelaajisto on muuttunut todella paljon, eikä joukkueessa ole vuoden 1999 mestarijoukkueesta jäljellä enää kuin Mike Modano, Sergei Zubov sekä Jere Lehtinen. Menestystä ei ole tullut toivotulla tavalla ja siitä voidaan suurimmaksi osin syyttää Dallasin keskinkertaisia pelaajavarauksia.
Todellisia helmiä organisaation draft-historiassa on vain muutamia. Jarome Iginla, jonka oikeudet kaupattiin aikanaan Calgaryyn vaihdossa Nieuwendykiin, ei pelannut joukkueessa peliäkään. Häntä voidaan silti pitää yhtenä Dallasin parhaista varauksista, kuten myös kolminkertaista Selke-voittajaa Jere Lehtistä, All-Star -maalivahti Marty Turcoa sekä Olympiakultamitalisti Brenden Morrow'ta.
Kauden 2005-2006 alkaessa Dallasilla on jälleen kerran mahdollisuus menestyä. Se vaatii jokaiselta avainpelaajalta huippukautta ja lisäksi ripauksen onnea. 1990-luvun lopun tasoista joukkuetta ei nimittäin vähään aikaan Teksasissa tulla näkemään.
