Do Edmontonu přišel Gretzky na podzim roku 1978 a sotva dosáhl v lednu 1979 plnoletosti, podepsal s ním majitel klubu Peter Pocklington smlouvu za tři milióny dolarů ročně po následujících deset let s možností držet si jej až do roku 1999!!!
Vskutku velmi lichotivé vyznamenání pro osmnáctiletého mladíčka, který se v profesionálním hokeji teprve rozkoukával. Ale Pocklington dobře věděl, co dělá – Gretzky během první sezóny ve WHA nasbíral přes sto bodů, dalších dvacet získal v play off a byl vyhlášen nejlepším nováčkem soutěže.
Předčil tak mnohem zkušenější borce v týmu. Úžasného zážitku se mu dostalo druhý lednový den roku 1979, kdy nastoupil v týmu hvězd WHA proti Dynamu Moskva. Vedl útok Gordie Howe, Gretzky, Mark Howe a oblékl stejný dres jako jeho největší idol. Ročníkem 1979-80 byl Edmonton společně s Quebecem, Winnipegem a Hartfordem přijat mezi smetánku NHL a ani tam se Gretzky neztratil. Nejmladší hráč ligy překonal svůj první rekord NHL už 15. února 1980 sedmi přihrávkami v jednom zápase.
Až do konce základní části bojoval s Marcelem Dionnem z Los Angeles o vítězství v kanadském bodování. Oba měli na konci základní části 137 bodů, ale Art Ross Trophy nakonec získal Dionne, protože vstřelil o dvě branky více. Gretzkému utekla i Calder Trophy pro nejlepšího nováčka, protože mu vedení NHL oznámilo, že jeho předchozí sezóna ve WHA byla započítána jako rok profesionálního hokeje, čili nemůže být vyhlášen nejlepším nováčkem dvakrát po sobě.
Cenu získal později neméně úspěšný zadák Bostonu Ray Bourque. Nicméně Gretzkému nebyla upřena výborná sezóna a získáním Hart Trophy byl oceněn jako nejlepší hráč soutěže. Nikomu v historii NHL se nikdy předtím ani potom nepovedlo získat tuto trofej hned v prvním roce v NHL. Gretzky byl spokojen i v civilním životě, protože do sestavy „Oilers“ se po čtyřech zápasech v Central Hockey League nastálo probojoval edmontonský rodák Mark Messier a společně s Gretzkým si „mladé naděje kanadského hokeje“ dosyta užívaly ve společném bytě.
Hart Trophy Gretzky v následujícím roce obhájil a byl jako nejlepší oceňován až do roku 1988, kdy se na scéně objevil nový idol – Mario Lemieux. Ve své druhé sezóně mu byla konečně přiznána Art Ross Trophy, když ziskem 164 bodů překonal rekord Phila Esposita z roku 1971 (152). Také cena pro nejproduktivnějšího hráče nenosila do roku 1988 jiný štítek než s jménem Gretzky. Naprostým zlomem historie kanadského bodování NHL byla sezóna 1981-82, kdy jednadvacetiletý Gretzky překonal zdánlivě nemožnou hranici 200 kanadských bodů za branky a přihrávky . Když mu k úžasným 92 brankám napočítali ještě sto dvacet přihrávek, vyšlo fenomenální číslo 212!!! To znamenalo, že na tehdejších 417 brankách Edmontonu se sám Gretzky podílel více jak z poloviny!!! Gretzky ve stejném roce rovněž překonal další magické číslo – vstřelit padesát branek maximálně ve stejném počtu zápasů. Podařilo se mu to 30. prosince 1981 proti Philadelphii. V jediném zápase dokázal nastřílet pět branek, poslední tři sekundy před koncem a po 39 zápasech měl na kontě rovnou padesátku gólů. Gretzkého úspěchy ocenila i celá americká sportovní veřejnost a časopis Sports Ilustrated jej zvolil nejlepším sportovcem roku 1982.
Zatímco Gretzky sbíral jedno individuální ocenění za druhým a s neuvěřitelnou lehkostí bořil mýty a rekordy soutěže, samotný Edmonton na svůj výrazný úspěch teprve čekal. A to přestože už začátkem osmdesátých let měl ve svém středu řadu vynikajících hráčů: kromě Gretzkého a Messiera třeba Fina Jari Kurriho, nejofenzivnějšího obránce od dob Bobby Orra, Paula Coffeyho, Glenna Andersona, Kevina Lowea nebo skvělého brankáře černé pleti Granta Fuhra. Největším úspěchem byla účast ve finále Stanley Cupu v sezóně 1982-83, ale famózní generace New York Islanders tehdy smetla Edmonton 4:0 na zápasy. O rok později se Edmonton s týmem Mikea Bossyho, Denise Potvina a Bryana Trottiera utkal znovu a tentokrát se radovala Kanada, protože do nejhokejovější země světa se Stanley Cup vrátil po pěti letech od slavných dob Montrealu. Jako první zdvihl nad hlavu slavný „křapáč“ nový kapitán „Oilers“ Wayne Gretzky. Konečně umlčel všechny kritiky, kteří mu neustále předhazovali, že neumí vyhrávat klíčové zápasy a že bez Stanley Cupu se nikdy nestane velkým hráčem.
Slavné vítězství oslavilo naftařské město i v roce 1985, tentokrát po výhře nad Philadelphií (4:1) a stejně jako před rokem se z vítězství radoval i čs. reprezentant Jaroslav Pouzar, jehož hru na pravém křídle svého útoku si Gretzky toho času velmi pochvaloval. Během osmdesáti zápasů základní části ročníku 1985-86 dokázal „Great One“ nasbírat 215 bodů a překonal svůj vlastní čtyři roky starý rekord o tři body. Vítězství v kanadském bodování by Gretzky dokonce dosáhl i pouhým počtem asistencí – k číslu 163 se dokázal nejvíce přiblížit jen Mario Lemieux (141 bodů)!!! Jen pro zajímavost – celý tým Detroitu tehdy dokázal nastřílet o necelých padesát branek víc, než na kolika se podílel sám Gretzky!! Smutnou kaňkou roku bylo vyřazení Edmontonu ve čtvrtfinále play off s Calgary. Na konci sezóny 1986-87 byl Edmonton nejlepším týmem základní části a přes Los Angeles, Winnipeg a Detroit se probojoval do finále Stanley Cupu proti Philadelphii. „Oilers“ vedli už 3:1 na zápasy, ale Philadelphia se vzpamatovala a poprvé za posledních šestnáct let měl o vítězi NHL rozhodnout sedmý zápas. V hale Northland Coliseum v Edmontonu se z první branky radovali „Flyers“, ale byla to jejich poslední trefa v zápase a ze třetího zisku Stanley Cupu se radovali domácí. Gretzky pak předvedl sklizeň trofejí: poosmé v řadě (!) byl oceněn Hart Trophy, posedmé v řadě Art Ross Trophy a popáté Lester B. Pearson Award. Zařazení do All-Star soutěže už bylo samozřejmostí.
V Edmontonu začaly mezitím pomalu vyplouvat na povrch rozpory hráčů s trenérem a generálním manažerem Glenem Satherem. Kvůli jeho aroganci a přehlíživosti mužstvo před sezónou 1987-88 opustili Paul Coffey a Andy Moog a jeho neustálých kritik za výkony, kterými by se mohl každý hokejista pyšnit, už měl dost i Gretzky. Sather nemohl pochopit, proč jsou hokejisté narozdíl od jeho éry tak štědře placeni a neustále to Gretzkému předhazoval. Edmonton navíc začal být Gretzkému příliš těsný – neexistovalo pro něj soukromí a většinu času musel trávit doma. Šestnáctizápasovou přestávku vynucenou zraněním kolene proto alespoň využil k odpočinku od veškerého stresu. Do play off vstoupil zase s odhodláním, po vyřazení Winnipegu, těžkým zápasům s Calgary a přes Detroit, znovu se svými spoluhráči obhájit titul. Boston ve finále vyřídili 4:0 na zápasy a Edmonton ve svém devátém roce v NHL oslavoval čtvrtý Stanley Cup. Tehdy Gretzky jistě netušil, že je jeho poslední.
V červenci 1988 se Gretzky oženil s americkou herečkou Janet Jonesovou. Svatbu tehdy sledovala celá Kanada a všichni byli zvědavi, koho si ten „jejich“ chlapec vlastně bere. Chvíle velkého štěstí trvaly necelý měsíc. Devátého srpna svolalo vedení Edmontonu tiskovou konferenci a majitel „Oilers“ Peter Pocklington novinářům oznámil, že právě prodal kapitána svého týmu do Los Angeles za 15 milionů dolarů! Pocklingtonovy obchody s prodejem nafty, balením masa nebo podílech na autech se ocitly ve vážných potížích a jejich šéf potřeboval hotovost… Hokejová Kanada cítila zradu a spousta fanoušků, stejně jako samotný Gretzky na tiskovce, neudržela slzy smutného loučení…