לעונת 98–1997 שכרו המג'יק את צ'אק דיילי לתפקיד המאמן הראשי. בנוסף, חבר היכל התהילה, ג'וליוס ארווינג הצטרף להנהלת המועדון. פעולות אלה נתו למג'יק תקוות גדולות לעונה שבפתח. אך העונה הייתה מלווה בפציעות, כאשר הארדוויי נאלץ לצפות מהספסל ברוב משחקי העונה. אנדרסון, יחד עם הרכש החדש שהיה שחקן חופשי בו אאוטלו, הובילו את הקבוצה למאזן המכובד של 41-41, והחמיצו במעט את הפלייאוף. בנוסף, רוני סייקלי הועבר במהלך העונה לניו ג'רזי נטס תמורת שלושה שחקנים ובחירת דראפט אחת.
בעונת 99–1998, עם בחירתם של מייקל דוליאק ומאט הארפרינג כבחירות ה-12 וה-15 בדראפט של שנת 1998 (בהתאמה), עם הארדוויי הבריא ואנדרסון, השתוו המג'יק למיאמי היט במאזן הטוב ביותר באזור המזרח בעונה המקוצרת עקב שביתת השחקנים, במאזן של 17–331. ארמסטרונג הוביל שוב את הקבוצה עם יכולותיו האמוציונאליות, כשהוא זוכה בפריסי השחקן השישי של העונה והשחקן המשתפר של העונה. בנוסף, רכש המג'יק אחד השחקנים הגדולים בתולדות ה-NBA, דומיניק וילקינס, יחד עם אחיו ג'רלד וילקינס, שניהם היו מעבר לשיאם אך עדיין נחשבו לשחקנים טובים. בפלייאוף דורגו המג'יק במקום השלישי לאחר השוויון על ההיט ופגשו את הפילדלפיה 76'. פילדלפיה, בהובלתו של אלן אייברסון, הפתיעו את המג'יק וגברו עליהם 1–3 בסיבוב הראשון. המועדון גם החליט לשנות את צבעי המועדון לראשונה בתולדות המועדון והחליף את צבעי הפסים בכוכבים.
בשנת 1999, המג'יק, תחת ניהולו הג'נרל מנג'ר ג'ון גבריאל, שמאוחר יותר נבחר למנהל השנה, שכר את המאמן הצעיר דוק ריברס. גבריאל פרק את שארית הקבוצה הקודמת של המג'יק ושלח את הארדוויי בטריי לפיניקס סאנס תמורת דני מאנינג (שמעולם לא לבש את מדי המג'יק), ופאט גאריטי ושתי בחירות דראפט עתידיות. המג'יק הפכו לקבוצה בעלת סגל שחקנים לא מוכר ושאינו מנוסה כאשר את סרט הקפטן ענד בו אאוטלו ובן וולאס הצעיר, יחד עם המאמן ריברס הם הובילו את המג'יק למאזן של 41-41, והחמיצו במעט את הפלייאוף. בסופה של העונה נבחר ריברס למאמן השנה בעונה זו דבק הסלוגן בקבוצה, "לב ודחיפה", כאשר הקבוצה נודעה בעבודה הקשה של סגנון משחקה.
2000-2004: עידן טרייסי מקגריידי.
בפגרה שלאחר מכן, גבריאל, שלרשותו עמד מרווח גדול מתקרת השכר של הליגה, ניסה לפתות שלושה שחקנים שהפכו לחופשיים עם סיומה של העונה: טים דאנקן, גרנט היל, וטרייסי מקגריידי. אף על פי שדאנקן העדיף להישאר בסן אנטוניו ספרס, רכשו המג'יק את היל, שהיה שחקן אול סטאר קבוע, ואת מקגריידי. עם מקגריידי והיל יחדיו, הייתה הציפייה כי המג'יק יהפכו לכוח דומיננטי במזרח. אך, היל שסבל מבעיית קרסול החמיץ את רובה של העונה ושיחק רק ארבעה משחקים. במהלך העונה פרחמקגריידי והפך לכוכב, והפך לקלע המוביל של הליגהץ עם התוספת של מייק מילר שהגיע מהדראפט, הצליחו המג'יק להגיע למאזן של 39–43, שכלל ריצה של תשעה ניצחונות רצופים, והגיעו שוב אל משחקי הפלייאוף. מקגריידי נבחר למשחק האול סטאר ונבחר לחמישייה השנייה של העונה. מילר זכה בפרס רוקי השנה באותה העונה. בפלייאוף, פגשו המג'יק בסיבוב הראשון את המילווקי באקס שהיו לכוח עולה באותה עונה, הבאקס ניצחו בסדרה 1–3.
בעונת 02–2001 הוביל מקגריידי את המג'יק למאזן של 38–44. אך, היל עדיין היה מוגבל מאוד עקב פציעת הקרסול ממנה המשיך לסבול, ולא שיחק במשך רובה המכריע של העונה. מקגריידי, יחד עם ארמסטרונג, מילר, וקלעי שלוש הנקודות המצטיין פאט גאריטי, יצרו את בסיס הקבוצה לאותה עונה. מקגריידי, נבחר לחמישיית העונה לראשונה בקריירה ונבחר בפעם השנייה ברציפות למשחק האול סטאר. אך, המג'יק נוצחו שוב בסיבוב הראשון של הפלייאוף בידי השארלוט הורנטס, בהנהגתו של בארון דייוויס בתוצאה 1–3.
בעונת 03–2002, עם רכישתו של גורדן גיריצ'ק ודרו גודן מהממפיס גריזליס בתמורה למייק מילר, הובילמקגריידי שוב את המג'יק למאזן של 40–42. מקגריידי הוביל את הליגה בנקודות כשהוא משיג 32.1 נקודות למשחק בממוצע, נבחר בפעם השנייה לחמישיית העונה, ומופיע בפעם השלישית במשחק האול סטאר. על אף שעדיין סבלו מהיעדרותו של היל עקב פציעת הקרסול הטורדנית ממנה סבל, הצליחו המג'יק להגיע אל משחקי הפלייאוף עונה שלישית ברציפות. אך, לאחר שהוביל 1–3 בסדרה של הטוב מ-7 משחקים, גמגמו המג'יק ונוצחו 3–4 בסיומה של הסדרה בידי הדטרויט פיסטונס. בסיומה של הסדרה צוטט מקגריידי שאמר: "זה יכול להיות נחמד להגיע פעם לסיבוב השני" לאחר שהקבוצה נזקקה רק לניצחון אחד נוסף כדי להתקדם.
עונת 04–2003 הייתה עונתם ה-15 של המג'יק והתבררה כאחת העונות הקשות ביותר בתולדות המועדון. גם לאחר רכישתם של השחקנים החופשיים הוותיקים טיירון לו, וג'וואן הווארד, השתרכו המג'יק בשלב מוקדם של העונה. לאחר שנצחו במשחק הראשון, הפסידו המג'יק ב-19 משחקים ברציפות, קובעים שיא מועדון שלילי. המג'יק סיימו את העונה במאזן 21–61 מאכזב, הגרוע בליגת ה-NBA. למרות זאת, סיים מקגריידי את העונה כקלעי המוביל של הליגה, כשהוא משיג 28.0 נקודות בממוצע למשחק, מקגריידי לנבחר לחמישיית השנייה של העונה ולמשחק האול סטאר בפעם הרביעית ברציפות. באמצע רצף 19 ההפסדים של המג'יק במהלך העונה, פוטר המאמן דוק ריברס, ועוזר המאמן ג'וני דייוויס קודם במקומו. בנוסף הוחלף הג'נרל מנג'ר גבריאל בידי ג'ון וייסברוד.
2004-2006: התחלה חדשה עם דווייט הווארד.
במהלך הפגרה, פירק וייסברוד את קבוצה לחלוטין. על אף שדייוויס שמר על מקומו כמאמן הראשי של הקבוצה, הוא המם את השחקנים כאשר החליט לשמור רק מספר מצומצם של שחקנים מהעונה שעברה בסגל הקבוצה. הטרייד המשמעותי ביותר היה זה של טרייסי מקגריידי. מקגריידי לא היה שבע רצו באורלנדו, ביקש לעבור לקבוצה אחרת; וייסברוד האשים את מקגריידי ב"התרשלות מכוונת" ובחוסר השתתפות באימונים (מאוחר יותר הודה מקגריידי כי לא נתן 100% במהלך עונת 04–2003 ורצה כי המועדון יביא לו עזרה, אך מעולם לא רצה לעזוב את אורלנדו). המג'יק העבירו את מקגריידי יחד עם ריס גיינס, טיירון לו, וג'וואן הווארד ליוסטון רוקטס בתמורה לסטיב פרנסיס, קלווין קאטו, וקוטינו מובלי, בנוסף רכשו המג'יק את הסנטר טוני באטי ושתי בחירות סיבוב שני מהקליבלנד קאבלירס בתמורה לדרו גודן, סטיבן האנטר, וזכויות הדראפט על אנדרסון וראג'ו. המג'יק החתימו גם את הידו טורקוגלו. עם בחירת הדראפט הראשונה, בחרו המג'יק את כוכב ליגת התיכוניים, דווייט הווארד והעבירו אליהם גם את הפויינט גארד ג'מיר נלסון. נלסון, שרבים מהפרשנים ציפו כי יבחר בין עשרת הראשונים בדראפט נפל לבחירה ה-20, והמג'יק העבירו לדנוור נאגטס בחירת סיבוב ראשון עתידית בתמורה.
לאחר פתיחה מבטיחה של 6–13, החלו המג'יק להתפרק. תחילה, העביר וייסברוד את מובלי לסקרמנטו קינגס תמורת דאג כריסטי. כריסטי, סירב תחילה לשחק בעבור המג'יק עקב קשריו הרגשיים לקינגס. מאוחר יותר, טען כריסטי כי הוא סובל מדורבן והוצב ברשימת הפצועים לאחר ששיחק רק משחקים בודדים בעבור המג'יק. לקראת סופה של העונה, כאשר מאמצי הפלייאוף תלויים על בלימה, פיטר וייסבורד את דייוויס לאחר שהוביל את דייוויס להאמין כי הוא אמור להישאר המאמן הראשי של הקבוצה עד לסוף עונת 05–2004. לאחר מכן, הוא קידם את כריס ג'נט לתפקיד מאמן ראשי זמני. לאורך העונה, חזרתו של היל הגביהה את רף הציפיות בקבוצה, והקבוצה שיחקה טוב למדי. המג'יק גברו במהלך העונה על קבוצות מצמרת הליגה כסן אנטוניו ספרס, דאלאס מאבריקס, מיאמי היט, פיניקס סאנס, ודטרויט פיסטונס. אך, בהתאם למסורת הבלתי יציבה של המועדון, הפסידו המג'יק גם לקבוצות בעלות מאמזן שלילי כמו קבוצת ההרחבה שארלוט הורנטס ואטלנטה הוקס. אך, הווארד הראה הבטחה גדולה, והפך לאחד השחקנים הבודדים המסיימים את העונה הסדירה עם ממוצעים של דאבל דאבל (בנקודות ובכדורים חוזרים). הווארד הפך לקולט כדורים חוזרים וספק נקודות מתמיד, הופך לרוקי הראשון בהיסטוריה של הליגה המשחק בחמישייה הפותחת בכל 82 משחקי העונה הסדירה. בנוסף, נלסון, לאחר התחלה איטית, הפך לשחקן מוכשר, תופס את עמדת הפויינט גארד הפותח של הקבוצה. היל חזר והשיג ממוצעים נאים של 19.7 נקודות למשחק. היל נבחר לחמישייה הפותחת במשחק האול סטאר של שנת 2005 על ידי האוהדים, ודווייט הווארד וג'מיר נלסון נבחרו לחמישיית הראשונה והשנייה של הרוקיז, בהתאמה, כאשר הווארד נבחר בתמימות דעים.
המג'יק סיימו את העונה במאזן 36–46, מאזן מאכזב בהשוואה לפתיחת העונה החזקה. המאמץ לבגיע אל הפלייאוף סוכל על ידי פציעות ברבע האחרון של העונה: השחקן השישי של המג'יק, הידו טורקוגלו שבר את פרק ידו לקראת סופה של העונה, פציעת שוק של היל, פציעת צלעות לנלסון, והשעייה לשלושה משחקים אותה קיבל פרנסיס לאחר שכביכול בעט בצלם. בסופה של העונה הסדירה, סיימו המג'יק בפיגור של כמה ניצחונות ממקום המוביל לפלייאוף. אך, ב-23 במאי, תוכניותיהם של המג'יק נעצרו לאחר התפטרותו הפתאומית של הג'נרל מנג'ר ג'ון וייסבורד. בנוסף, ביום למחרת הודיעה הנהלת המועדון כי בראיין היל, המאמן שהוביל את המיאמי היט, עם שאקיל אוניל ופני הארדוויי, לגמר ה-NBA, יחזור אל המועדון בתפקיד המאמן הראשי.