גרצקי המשיך לשלוט בליגה גם בעונת 1985, זכה שוב בגביע הארט ובגביע ארט רוס (עם 208 נקודות), קורי כבש 71 שערים וצבר 135 נקודות, וקופי שוב הצטיין ביכולת התקפית מעמדת המגן עם 121 נקודות. האוילרס סיימו את העונה הרגילה עם 109 נקודות בטבלה, המאזן השני בטיבו בליגה, וניצחו בשתי סדרות הפלייאוף הראשונות שלהם מול לוס אנג'לס קינגס וויניפג ג'טס בלי להפסיד ולו משחק אחד. שיקגו בלאקהוקס, בגמר החטיבתי, הייתה היחידה שהקשתה על האוילרס וגררה אותם לשישה משחקים לפני שהאוילרס הדיחו גם אותה וחזרו בפעם השלישית ברציפות לסדרת גמר גביע סטנלי מול פילדלפיה פליירס. אחרי הפסד במשחק הראשון ניצחו האוילרס בארבעת הבאים, וזכו בגביע סטנלי בפעם השנייה ברציפות. גרצקי קבע שיא חדש כשצבר 47 נקודות בפלייאוף, וזכה בגביע קון סמיית'.
האוילרס המשיכו להבקיע בהספק מרשים גם בעונת 1986, כאשר סיימו את הליגה עם המאזן הטוב ביותר וזכו בגביע הנשיאים בפעם הראשונה שגביע זה חולק. גרצקי, קורי ואנדרסון שוב עברו את 50 השערים כל אחד, כאשר קורי סיים עם 68 שערים, ופול קופי קובע שיא שערים חדש עבור מגן עם 48. שוב מעל כולם היה וויין גרצקי, ששבר את שיאיו-שלו באסיסטים (163) ונקודות (215), וזכה בגביע הארט שביעי רצוף ובגביע ארט רוס שישי רצוף. בפלייאוף הביסו האוילרס את ונקובר קנאקס, אולם בסיבוב השני הופתעו על ידי קלגרי פליימס בשבעה משחקים והודחו. לשער ההפסד, לקראת סיום המשחק השביעי והמכריע, גרם דווקא המגן הרוקי של האוילרס, סטיב סמית, שהכה את הדיסקית בטעות לתוך שערו-שלו.
עונת 1987 המשיכה את המגמות של השנים הקודמות. האוילרס זכו בפעם השנייה ברציפות בגביע הנשיאים כשסיימו את העונה הרגילה עם המאזן הטוב בליגה. גרצקי, קורי ומסיה דורגו 1, 2 ו-4 בהתאמה בדירוג המבקיעים של הליגה. גרצקי זכה בגביע הארט שמיני רצוף ובגביע ארט רוס שביעי רצוף, והחלוץ הפיני אסה טיקנן סייע בידם עם עונת פריצה של 78 נקודות. פיור ומוג המשיכו לחלוק בעמדת השוער. האוילרס עלו בקלות עד לסדרת הגמר של גביע סטנלי, כאשר בדרך הם מדיחים את לוס אנג'לס קינגס, ויניפג ג'טס ודטרויט רד וינגס עם שני הפסדים בלבד בשלוש הסדרות גם יחד. בסדרת הגמר פגשו האוילרס שוב את פילדלפיה פליירס. יכולת מצוינת של שוער הפליירס רון הקסטול גררה את הסדרה למשחק שביעי ומכריע, בו ניצחו האוילרס וזכו בגביע סטנלי בפעם השלישית. הקפטן גרצקי לקח איתו לטקס הנפת הגביע את סטיב סמית, המגן הצעיר שטעות שלו גרמה להדחת האוילרס מהפלייאוף בעונה הקודמת.
עונת 1988 החלה את תהליך התפרקות השושלת. פול קופי, המגן המצטיין, שבת מפעילות בעקבות סכסוך חוזי עם הקבוצה ולבסוף הועבר לפיטסבורג פינגווינס. גם השוער אנדי מוג, שלא היה מרוצה מחלוקת עמדת השוער עם גרנט פיור, בחר לעזוב ועבר לבוסטון ברואינס. במקומו הגיע מבוסטון ביל רנפורד, שהפך לשוערו המחליף של פיור. פיור עמד בעומס, הפגין יכולת גבוהה וזכה בגביע וזינה - גביע שוער העונה. גרצקי המשיך להיות המבקיע המוביל של הקבוצה, אולם לראשונה מזה שמונה עונות לא היה המבקיע המצטיין בליגה ולא זכה בגביע ארט רוס. גם תואר ה-MVP וגביע הארט לא היו נחלתו של גרצקי באותה עונה. למרות הזעזועים שעברה הקבוצה, היא נהנתה מעליונות מוחלטת בפלייאוף כאשר הדיחה בקלות יתרה את ויניפג ג'טס, קלגרי פליימס ודטרויט רד וינגס בדרך לסדרת גמר נוספת, וגם אותה ניצחו בקלות מול בוסטון ברואינס בלא להפסיד ולו משחק אחד. האוילרס הפסידו שני משחקים בלבד בכל ארבע הסדרות, והשלימו ארבע זכיות בגביע סטנלי בחמש עונות.
עם זאת, האירוע המשמעותי ב-1988 קרה בקיץ שאחרי העונה - עסקה שהותירה את חותמה על ה-NHL ועל הספורט המקצועני הצפון-אמריקאי כולו.
ב-9 באוגוסט 1988 הודיעו בעלי האוילרס על העברתו של וויין גרצקי ללוס אנג'לס קינגס, בעסקה שכללה שחקנים נוספים, סכום כסף ומבחר גדול של בחירות דראפט גבוהות שעברו לאוילרס. מעברו של גרצקי, שכונה בפשטות "ה-עסקה", הכה גלים בכל קנדה עד כדי קריאות בפרלמנט הקנדי למנוע את העסקה. עצם המעבר מקבוצה גדולה כמו האוילרס דאז דווקא לקינגס, קבוצה חסרת הצלחות שנחשבה לנידחת בליגה, והתבססה בעיר חמה שלא הייתה שוק הוקי קרח טבעי, רק הוסיף לתדהמה מהעסקה. האוילרס נאלצו להמשיך את דרכם ללא מי שכבר נחשב לשחקן ההוקי קרח הטוב ביותר בעולם.
עם מרק מסיה כקפטן במקומו של גרצקי, סיימו האוילרס רק במקום השלישי ב"בית סמיית'" את העונה הסדירה של 1989, וכך הזדמן להם, במקרה, מפגש פלייאוף מול גרצקי וחבריו החדשים מלוס אנג'לס קינגס כבר בסיבוב הראשון. האוילרס עלו ליתרון 3:1 בסדרה, אולם בהנהגתו של גרצקי ניצחו הקינגס בשלושת המשחקים הבאים תוך כיבוש 14 שערים והדיחו את האוילרס.
בעונת 1990 הוכיחו האוילרס, ובמיוחד הקפטן מרק מסיה, שהתאוששו מעסקת גרצקי. גרנט פיור נפצע בתחילת העונה, וביל רנפורד גילה יכולת גבוהה ותפס את מקומו. מסיה סיים כ-MVP של העונה וזכה בגביע הארט, והיה שני בדירוג המבקיעים, אחרי גרצקי.
בסיבוב הראשון, מול ויניפג ג'טס, היו האוילרס על סף הדחה כאשר פיגרו 3:1 בסדרה ו-3:1 במשחק החמישי. למרות זאת הצליחו להפוך את המשחק החמישי ולנצח גם את השניים הבאים כדי לנצח בסדרה כולה. בסיבוב השני פגשו שוב את לוס אנג'לס קינגס עם וויין גרצקי, והפעם לא הותירו לקפטן שלהם לשעבר שום סיכוי כשהביסו את הקינגס בארבעה משחקים. בגמר החטיבתי ניצחו האוילרס את שיקגו בלאקהוקס בשישה משחקים, ועלו לסדרת גמר גביע סטנלי בפעם השישית, מול בוסטון ברואינס.
המשחק הראשון בסדרת הגמר הפך למשחק הפלייאוף הכי ארוך בתולדות ה-NHL, כאשר האוילרס כבשו את שער הניצחון בו 4 דקות ו-47 שניות לסיום ההארכה השלישית. הם המשיכו וניצחו בסדרה בחמישה משחקים, וזכו בגביע סטנלי החמישי שלהם, והראשון ללא וויין גרצקי. השוער רנפורד, שגילה יכולת גבוהה מאוד לאורך הפלייאוף, נבחר ל-MVP של הפלייאוף וזכה בגביע קון סמיית'.
1991 - 1992: שולי ההצלחה.
את עונת 1991 העבירו האוילרס ללא החלוץ הפיני הוותיק יארי קורי, שבעקבות סכסוך חוזי עם הקבוצה עבר לשחק באיטליה. האוילרס סיימו במאזן בינוני את העונה הרגילה, אולם בפלייאוף הפתיעו את יריבתם הגדולה קלגרי פליימס בסדרה שהגיעה למשחק שביעי שהוכרע בהארכה. בסיבוב השני פגשו, זו השנה השלישית ברציפות, את לוס אנג'לס קינגס עם גרצקי, ופעם השנייה ברציפות ניצחו האוילרס בסדרה. בגמר החטיבתי נעצרו האוילרס על ידי מינסוטה נורת'סטארס.
השחקנים שהרכיבו את שושלת שנות ה-80 המשיכו לעזוב. יארי קורי שחזר מאיטליה עבר לשחק עם גרצקי בלוס אנג'לס קינגס. גלן אנדרסון וגרנט פיור עברו לטורונטו מייפל ליפס, והקפטן מרק מסיה עבר לניו יורק ריינג'רס. גם המאמן ביל מאקלר עזב. למרות כל זאת, העונה של האוילרס דמתה לקודמת - מאזן פושר בעונה הרגילה ועלייה עד לגמר החטיבתי בפלייאוף, תוך ששוב הם עוברים בדרך את לוס אנג'לס קינגס וגרצקי. בגמר החטיבתי הובסו האוילרס על ידי שיקגו בלאקהוקס.
1993 - 1996: שנות השקיעה.
לקראת עונת 1993 עזבו אחרוני כוכבי השושלת את הקבוצה. קווין לואו ואסה טיקנן חברו לקפטן הקודם שלהם, מרק מסיה, בניו יורק ריינג'רס. על השינויים המצטברים כבר לא יכלו האוילרס להתגבר, ולמרות עלייתם של כוכבים צעירים כדאג ווייט וג'ייסון ארנוט והגעתו של השוער המוכח קרטיס ג'וזף, האוילרס סיימו את העונות הרגילות במאזנים חלשים והחמיצו במשך ארבע עונות רצופות את הפלייאוף. עונת 1993 הייתה העונה הראשונה בה האוילרס לא עלו לפלייאוף מאז שהצטרפו ל-NHL.
1997 - 2004: חזרה לפלייאוף.
בעזרת עונה טובה של קרטיס ג'וזף בשער, חזרו האוילרס לפלייאוף בעונת 1997, שם הפתיעו בסיבוב הראשון את דאלאס סטארס. בסיבוב השני נוצחו על ידי האלופה היוצאת קולורדו אוולאנש. ג'וזף, יחד עם שחקני הרכש ביל גרין ורומן המרליק, העלו את האוילרס לפלייאוף גם בעונה שלאחר מכן, שם התהפכו היוצרות - האוילרס הדיחו במפתיע את האוולאנש, והודחו על ידי הסטארס. בתום אותה עונה עזב ג'וזף את הקבוצה. למרות חסרונו של שוער ברמה גבוהה האוילרס הצליחו לעלות בקושי לפלייאוף של עונת 1999, שם הובסו שוב על ידי הסטארס כבר בסיבוב הראשון.
באותה תקופה סבלה הקבוצה ממצב כלכלי קשה ועמדה על סף מכירה ומעבר לעיר בארצות הברית. בעקבות מעברן של קוויבק נורדיקס לדנוור ושל ויניפג ג'טס לפיניקס נשארו האוילרס הקבוצה עם השוק הקטן ביותר ב-NHL, והבעיות שהעיקו על השתיים הקודמות - ירידת ערך של הדולר הקנדי, מיסים גבוהים מאוד ביחס לארצות הברית, ומשכורות שחקנים שעלו במידה ניכרת - העיקו גם על האוילרס. הבעלים פיטר פוקלינגטון ניסה להעביר את הקבוצה למינסוטה, ולאחר מכן ניהל משא ומתן מתקדם עם לזלי אלכסנדר, בעלי קבוצת ה-NBA יוסטון רוקטס, על מכירת הקבוצה לאלכסנדר והעברתה ליוסטון. לבסוף התגייסה קבוצת משקיעים מקומית שקנתה את הקבוצה, בעידוד ה-NHL, והשאירה אותה באדמונטון.
בעונות 2000 ו-2001 עלו האוילרס לפלייאוף ובשתי הפעמים נוצחו בסיבוב הראשון שוב על ידי דאלאס סטארס, כאשר בסיום עונת 2001 עזב את הקבוצה כוכבה דאג ווייט. עונת 2002 החלה בצורה טובה עד הפגרה ב-NHL בזמן אולימפיאדת החורף בסולט לייק סיטי, שם שיחק שוער הקבוצה טומי סאלו בנבחרת שוודיה, וטעות קשה שלו גרמה להדחתה המפתיעה של שוודיה ברבע הגמר על ידי נבחרת בלארוס. לאחר האולימפיאדה גילה סאלו יכולת חלשה לאורך שארית העונה, והאוילרס החמיצו במעט את הפלייאוף.