První pokus o NHL ve státě Minnesota vydržel 26 let. Výsledkem bylo sedmnáct účastí v play off a dvě finálové porážky.

Když v březnu 1965 oznámil prezident NHL Clarence Campbell rozšíření ligy na dvanáct mužstev, byla mezi uchazeči i skupina businessmanů v čele s Walterem Bushem Jr., jenž usilovala o licenci pro Twin Cities, spojená města Minneapolis a St. Paul, v Minnesotě. Walterovo vynaložené úsilí bylo úspěšné a v únoru 1966 se dočkal souhlasu pro vstup do soutěže. Vstupní poplatek byl tehdy dva miliony amerických dolarů. Název “North Stars” zvítězil ve veřejném hlasování. Je odkazem na motto státu Minnesota “L'Étoile du Nord” - hvězda ze severu. Během jednoho roku byla v Bloomingtonu postavena domácí hala s názvem Metropolitan Sports Center, později MET Center.

Žlutozelení vstoupili do NHL 11. října 1967 na ledě dalšího nováčka St. Louis. Utkání skončilo nerozhodně 2:2. První gól organizace vsítil Bill Masterton. O deset dní později se radovali z první výhry. Týmu se od začátku herně dařilo a v polovině sezony vedl tabulku Západní divize. Jenže pak přišla rána, ze které se mužstvo vzpamatovávalo jen velmi těžko. Dne 13. ledna 1968 během zápasu proti Seals upadl Masterton hlavou na led a utrpěl těžká zranění, kterým o dva dny později podlehl. Bylo mu pouhých 29 let. Tento incident je doposud jediným v historii NHL, kdy zranění způsobené v zápase skončilo smrtí hráče. Mastertonovi spoluhráči byli natolik otřeseni, že prohráli následujících šest utkání. Po smrti Mastertona ostatní hokejisté v lize prohlašovali, že začnou v zápasech nosit helmy, avšak zanedlouho na svá předsevzetí zapomněli. Jako uctění památky zesnulého útočníka Severních Hvězd vznikla o rok později Bill Masterton Memorial Trophy, trofej pro hráče, jenž prokáže největší oddanost hokeji. Většinou se jedná o případy, kdy jedinec překoná vážnou nemoc, či tragédii.

Po sportovní stránce působí první sezona Minnesoty poměrně úspěšně. Celkové čtvrté místo v divizi a vyřazení v semifinále Západní divize, kdy je dělil jeden zápas of finále Stanley Cupu, zanechalo velice dobrý dojem. V prvních letech existence postoupili do vyřazovací části pětkrát ze šesti pokusů. Tým se opíral o spolehlivého gólmana Gumpa Worsleyho, který měl za sebou štace v New York Rangers a Montreal Canadiens. Obranu řídil kapitán Ted Harris a v útoku zářili Bill Goldsworthy, Barry Gibbs, Jude Drouin, Danny Grant, Lou Nanne, Tom Reid, Dennis Hextall, strýc současného GM Philadelphie Rona Hextalla a J.P. Parise, otec útočníka Wild Zacha Pariseho.

Se vznikem World Hockey Association byl založen klub i v sousedním městě St. Paul s názvem Minnesota Fighting Saints. V oblasti vydrželi však pouze tři a půl roku a nikdy tak nevytvořili meziligovou rivalitu s North Stars.

Další půltucet sezon skončil přesně opačným výsledkem, když se Hvězdy prokousaly do pohárových bojů pouze jedenkrát. Návštěvnost prudce klesala a liga se obávala, že organizace zanikne. Z toho důvodu byli North Stars sloučeni s jiným strádajícím klubem, Clevelandem Barons. Majiteli klubu se stali bratři Gundovi, kteří původně vlastnili Barons. Vše ostatní, tedy název, logo a historické statistiky vycházely z organizace Hvězd. Několik nově příchozích hráčů, například brankář Gilles Meloche, Al MacAdam, nebo Mike Fidler, měli okamžitě pozitivní vliv na hru Minnesoty. Po draftování talentovaného Bobbyho Smithe se v Minnesotě začala rýsovat velmi zajímavá sestava. V roce 1980 se Hvězdy probily do konferenčního finále, když předtím vyřadily ze hry šampiona z posledních čtyř let Montreal Canadiens. Pro další ročník se ke Stars připojil účastník Olympijských her v Lake Placid Neal Broten s kanonýrem Dinem Ciccarellim. S nimi v sestavě se Minnesota opět nadechla k jízdě vyřazovací částí, která skončila až ve finále Stanley Cupu na hokejkách favorizovaných New York Islanders. V průběhu osmdesátých let, kdy si vytvořila rivalitu s Chicagem, pokračovala Minnesota ve skvělých výkonech v základní části, ale v play off se už na podobnou jízdu nezmohla. V roce 1982 rozšířil sestavu Brian Bellows, jenž měl velmi dobrý vliv na ofenzívu. V sezoně 1983-84 byl dokonce součástí historického zápisu, kdy se svého času stal nejmladším kapitánem týmu v NHL, byť jen dočasným.

Ročník 1987-88 dopadl z pohledu Severních Hvězd katastrofálně, když dokázaly zvítězit pouze v devatenácti případech. To však znamenalo právo první volby v draftu. Minnesota si dle očekávání vybrala nejžádanějšího mladíka svého ročníku, Mika Modana. Modano se později stal nejlepším hráčem v historii organizace a měl lví podíl na největším úspěchu klubu, u nějž už však nebylo dopřáno být Minnesotským příznivcům.

Neuspokojivá návštěvnost domácích zápasů vedla majitele k úvahám o stěhování klubu. Bratři Gundovi, zamýšleli přesunutí do San Franciska, kde kdysi hrálo jejich původní mužstvo Golden Seals, ještě před stěhováním do Clevelandu. Liga však o dalším stěhování nechtěla ani slyšet. Kompromisem byl prodej Severních Hvězd třem novým majitelům a Gundovi získali povolení k novému klubu v oblasti Bay Area. Na cestu do severní Kalifornie si bývalí majitelé vzali polovinu původní soupisky, jenž se stala základem pro nový tým San Jose Sharks. Norman Green, nový většinový vlastník North Stars později vyplatil zbývající dva spolumajitele, aby se stal jediným mužem řídícím organizaci.

Na jaře 1991 dokázal tým zopakovat deset let starý úspěch v podobě finálové účasti. Tentokrát tomu bylo k překvapení všech, jelikož v lize bylo mnoho jiných favoritů. Na jaře jednadevadesátého roku poznaly formu Minnesoty postupně celky St. Louis Blues, Chicago Blackhawks a Edmonton Oilers. V celkovém finále narazili minnesotští na rozjetý Pittsburgh, který, v čele s Mario Lemiuxem na vrcholu sil, smetl Hvězdy v šesti zápasech, přičemž poslední zápas připomínal spíše exhibici, když Modano a spol. museli strpět osmigólový příděl. Nelichotivý výsledek 8:0 se zapsal do historie, když zápas, při kterém se rozhodlo o vítězi Stanley Cupu, skončil větším rozdílem naposledy v roce 1905.

Pro další sezonu přichystal majitel změnu loga, dresů a klubových barev. Původní bílé “N” nahradil znak hvězdy se zlatým nápisem “STARS”, z uniforem zmizela světle zelená a žlutá, již nahradila primární černá s bílými doplňky.

V roce 1992 Green zorganizoval prodej klubu do Los Angeles, avšak celá akce skončila kvůli společnosti Walt Disney, vlastnící licenci na nový tým Mighty Ducks of Anaheim, jenž se k soutěži připojil o rok později. Další pokus o přesun, nyní do Dallasu v lednu 1993, byl úspěšný. Za největší důvody přesunu označil Green slabou návštěvnost a neúspěšná jednání o výstavbě nové haly.
Dallas Stars si ponechali logo i dresy svých předchůdců. Během devatesátých let byla soupiska s Modanem v čele posílena o hráče jako Joe Nieuwendyk, Ed Belfour, nebo Brett Hull. Dallas si postupně začal podmaňovat NHL. Vrcholem bylo dobytí Stanley Cupu v roce 1999. V Minnesotě byli fanoušci bez vrcholového hokeje dlouhých sedm let, ale od roku 2000 jim dělají radost Minnesota Wild.