Obrovský úspěch North Stars v bojích o Stanleyův pohár 1991 v Minnesotě na čas oživil opadající zájem fanoušků o lední hokej. Ale přesto v roce 1993 nový majitel klubu Norm Green přestěhoval tým do Dallasu. V názvu týmu byl vynechán přívlastek North. Na novém působišti byli Stars prvním týmem NHL na půdě Texasu.

Trenér Bob Gainey, jehož ruský trenér Anatolij Tarasov jednou charakterizoval jako nejlepšího technického hráče. Zastával dvojí funkci trenéra a generálního manažera. Až do 8. ledna 1995, kdy post trenéra  předal K. Hitchcockovi. Hitchcock měl dobré výsledky v týmu Kalamazoo, který je farmou Stars v nižší lize. Pod vedením K. Hitchcocka se Stars poněkud zlepšovat, ale kvůli zranění stratily v jednom okamžiku oba hlavní brankáře Andyho Mooga a Darcyho Wakaluka a do Play-off se neprobojovali.

Oporami byli Mike Modano, který po čtvrté ve své sedmileté kariéře nastřílel soupeřům přes 30. branek, finský pravý ůtočník Jere Lehtinen, kterého mužstvo získalo v roce 92, ukázal záblesky svého umění v útočné i obranné hře.