האורלנדו מג'יק הצטרפו לליגת ה-NBA כקבוצת הרחבה בשנת 1989. תחרות שנערכה בחסות האורלנדו מג'יק, והעיתון אורלנדו סנטיאל איפשר לקהילה להציע שמות למועדון החדש. לתחרות הוצעו כ-4,300 שמות שצומצמו ל"היט", "טרופיקס", ג'וייס", ו"מגיק".[1] ב-27 ביולי 1986, הוכרז כי הוועדה בחרה את השם "מג'יק" שישמש את המועדון החדש מאורלנדו בליגת ה-NBA.[2] המג'יק היו אחד מארבעת המועדונים שזכו בזכות להצטרף לליגת ה-NBA יחד עם השארלוט הורנטס, המיאמי היט והמינסוטה טימברוולבס. תחילה, תכננה הנהלת הליגה להתרחב בשלוש קבוצות, כאשר אחד מהזיכיונות יגיע למדינת פלורידה; אך, כאשר גם קבוצות הבעלים של מיאמי וגם זו של אורלנדו הוקמו, החליטה וועדת ההרחבה של הליגה כי ארבעה מועדונים יצטרפו לליגה במקום שלושה, ואשרה לשתי קבוצות המשקיעים להקים קבוצות לליגת ה-NBA.[3] המג'יק הפכו למועדון הספורט הראשון מאזור העיר אורלנדו המשחק באחת מליגות הספורט הבכירות, וסכום הכניסה לליגה נקבע על 32.5 מיליון דולר.
המג'יק שכרו את מאט גאוקאס כמאמן הראשי הראשון של המועדון, והוא השתתף בבחירתם של שנים עשר השחקנים הראשונים לקבוצה בדראפט הרחבה מיוחד שהתקיים ב-15 ביוני 1989. ב-27 ביוני 1989 בחרו המג'יק את ניק אנדרסון בבחירה ה-11 בסיבוב הראשון של הדראפט, שהפכה לבחירת הדראפט הראשונה של המועדון.
ב-4 בנובמבר 1989 שיחקו המג'יק את משחק הליגה הראשון שלהם מול הניו ג'רזי נטס באורלנדו ארנה והפסידו 106–111. כמה ימים לאחר מכן, הגיע ניצחונם הראשון של המג'יק, כאשר גברו על הניו יורק ניקס 118-110. בשנה הראשונה השיגו המג'יק מאזן של 18–64 בתום העונה הסדירה כשבשורותיהם משחקים רג'י ת'יאוס, סקוט סקיילס, טרי קאטלדג', סם וינסנט, אוטיס סמית' וג'רי ריינולדס.[4][5] בדראפט של שנת 1990, בחרו המג'יק את דניס סקוט כבחירה הרביעית. ב-30 בדצמבר 1990 השיג סקוט סקיילס 30 אסיסטים בניצחון 116–155 על הדנוור נאגטס, ובכך שבר את שיאו של קווין פורטר למספר אסיסטים במשחק בודד (29).[6] סקיילס נבחר לשחקן המשתפר של העונה בסוף העונה, והמג'יק היו לקבוצה בעלת השיפור הגדול ביותר במאזנה באותה עונה. הפורוורד דניס סקוט קלע 125 סלים בשווי שלוש נקודות באותה עונה, וקבע שיא NBA לסלי שלוש נקודות בידי שחקן העונה הראשונה.[7] סקיילס נבחר לחמישיית הרוקיז של העונה. למרות המאזן השלילי של 31–51 בסיומה של העונה הסדירה, 40 מתוך 41 משחקי הבית של המג'יק נמכרו מראש.
ב-19 בספטמבר 1991 רכשה משפחת דהווס את שארית הבעלות על המועדון תמורת 85 מיליון דולר וראש המשפחה ריצ'רד דהווס הפך לבעלים של המועדון.[8] עונת 92–1991 הייתה מאכזבת עבור המג'יק, כאשר כמה שחקנים החמיצו משחקים רבים עקב פציעות. דניס סקוט שיחק רק 18 משחקים, ניק אנדרסון החמיץ 22 משחקים, סטנלי רוברטס, ג'רי ריינולדס, בראיין ויליאמס, סם וינסנט ואוטיס סמית' החמיצו לפחות 27 משחקים כל אחד. עם המחסור בשחקנים בריאים, דשדשה הקבוצה והפסידה 17 משחקים ברציפות. היא סיימה את העונה הסדירה במאזן של 21–61. למרות זאת עדיין הצליחו המג'יק למלא את אולם הביתי בכל משחק.
ההיסטוריה של המג'יק השתנתה ב-17 במאי 1992, כאשר המועדון זכה בבחירה הראשונה של הדראפט. המג'יק בחרו את הסנטר שאקיל אוניל מאוניברסיטת המדינה של לואיזיאנה, שנחשב ל"פרס" הגדול ביותר בדראפט מאז בחרו הניו יורק ניקס את פטריק יואינג.[9] שאקיל, סנטר המתנשא לגובה של 216 סנטימטרים, השפיע מיידית על המג'יק, והוביל את המועדון למאזן של 41-41.[10]המג'יק הפכו שוב למועדון המשתפר ביותר ב-NBA, והם השתפרו ב-20 משחקים יחסית לעונה שקדמה לה. אוניל היה לרוקי הראשון הנבחר לנבחרת האולסטאר מאז מייקל ג'ורדן בשנת 1985.[11] אוניל גם נבחר לרוקי השנה לעונת 93–1992. למרות נוכחותו של אוניל, החמיצה הקבוצה את משחקי הפלייאוף כיוון שסיימו את העונה הסדירה בשוויון עם האינדיאנה פייסרס במקום השמיני בדירוג פלייאוף המזרח, כאשר הפייסרס מחזיקים בשובר שוויון בעקבות מאזן טוב יותר במפגשים בין שתי הקבוצות.
אף על פי שהחמיצו כחוט השערה את משחקי הפלייאוף ועקב כך זכו לבחור את הכדור האחרון בהגרלת מיקום הקבוצות בבחירת הדראפט הקרובה, הצליחו המג'יק לזכות שוב בבחירה הראשונה בדראפט של שנת 1993. קודם לדראפט, עזב גאוקאס את תפקיד המאמן הראשי, ובמקומו מונה בראיין היל לתפקיד מאמנה השני של המג'יק.[12] בדראפט, בחרו המג'יק את כריס ובר, אך העבירו אותו לגולדן סטייט ווריורס תמורת הבחירה השלישית, הגארד פני הארדוויי ושלוש בחירות סיבוב ראשון עתידיות. עם השילוב של אוניל והארדוויי, הפכו המג'יק לקבוצה דומיננטית ב-NBA, כשהם משיגים את עונת 50 הניצחונות הראשונה בתולדות המועדון ומסיימים את העונה הסדירה במאזן של 32–50. המג'יק הצליחו להעפיל אל הפלייאוף בפעם הראשונה, כאשר הם מדורגים במקום הרביעי במזרח; אך הודחו כבר בסיבוב הראשון בידי האינדיאנה פייסרס לאחר שהובסו 0–3, וסיימו בכך את העונה.
בעונת 95–1994, עונתם השישית של המג'יק, נרכש שחקן האולסטאר הוראס גרנט כשחקן חופשי מהשיקגו בולס. המג'יק הצליחו להשיג מאזן של 25–57 בתום העונה הסדירה, הטוב ביותר במזרח, זכו בתואר האליפות של הבית האטלנטי והפכו למועדון השני המהיר ביותר המגיע לגמר ה-NBA בהיסטוריה של הליגה. בפלייאוף, נצחו המג'יק את הבוסטון סלטיקס, שיקגו בולס ואת האינדיאנה פייסרס, והתקדמו אל גמר ה-NBA. עם זאת, הם לא הצליחו לזכות באליפות, משום שהיוסטון רוקטס הביסו אותם 0–4 בגמר.
בעונת 96–1995, שוב היו המג'יק בפסגת המזרח והבית האטלנטי כאשר סיימו את העונה הסדירה באזן 22–60, בהנהגתם של אוניל והארדווי; אך המג'יק דורגו במקום השני אחרי השיקגו בולס שסיימו את העונה הסדירה במאזן 72-10 הטוב ביותר בליגת הNBA עד אז. בינתיים, הג'נרל מנג'ר פאט ויליאמס קודם לתפקיד סגן נשיא המועדון והוחלף ב-29 באפריל 1996 בידי סגן נשיא פעולות הכדורסל במועדון, ג'ון גבריאל. בפלייאוף, לאחר שהמג'יק גברו על הדטרויט פיסטונס והאטלנטה הוקס, פגשו המג'יק את הבולס בגמר המזרח. מול שילוב של ג'ורדן, סקוטי פיפן, ודניס רודמן, נחלו המג'יק תבוסה של 0–4 בגמר המזרח.
1996-2000: עידן פני הארדוויי
במהלך הפגרה, עזב שאקיל אוניל כשחקן חופשי ועבר ללוס אנג'לס לייקרס, מותיר אחריו חור עצום בקבוצה. במהלך אמצע העונה, ובעידודם של השחקנים שהפכו לבלתי מרוצים, פיטרה הנהלת המג'יק את המאמן בראיין היל ומינתה במקומו את ריצ'י אדובאטו כמאמן לתקופת ביניים לשארית העונה. תחת שרביט האימון של אדובאטו, הצליחו להשיג מאזן של 12–21 ולסיים את העונה במאזן של 37–45. את הקבוצה הנהיגו באותה עונה פני הארדוויי, דארל ארמסטרונג, המנהיג האמוציונאלי ורוני סייקלי שנרכש בגולדן סטייט ווריורס. בפלייאוף, התקרבו המג'יק וכמעט והצליחו להפתיע את מיאמי החזקה בסיבוב הראשון, כשהצליחו למשוך את הסדרה למשחק החמישי והמכריע, וזאת לאחר שהפסידו בשני המשחקים הראשונים.
לעונת 98–1997 שכרו המג'יק את צ'אק דיילי לתפקיד המאמן הראשי. בנוסף, חבר היכל התהילה, ג'וליוס ארווינג הצטרף להנהלת המועדון. פעולות אלה נתו למג'יק תקוות גדולות לעונה שבפתח. אך העונה הייתה מלווה בפציעות, כאשר הארדוויי נאלץ לצפות מהספסל ברוב משחקי העונה. אנדרסון, יחד עם הרכש החדש שהיה שחקן חופשי בו אאוטלו, הובילו את הקבוצה למאזן המכובד של 41-41, והחמיצו במעט את הפלייאוף. בנוסף, רוני סייקלי הועבר במהלך העונה לניו ג'רזי נטס תמורת שלושה שחקנים ובחירת דראפט אחת.
בעונת 99–1998, עם בחירתם של מייקל דוליאק ומאט הארפרינג כבחירות ה-12 וה-15 בדראפט של שנת 1998 (בהתאמה), עם הארדוויי הבריא ואנדרסון, השתוו המג'יק למיאמי היט במאזן הטוב ביותר באזור המזרח בעונה המקוצרת עקב שביתת השחקנים, במאזן של 17–33. ארמסטרונג הוביל שוב את הקבוצה עם יכולותיו האמוציונאליות, כשהוא זוכה בפרסי השחקן השישי של העונה והשחקן המשתפר של העונה. בנוסף, רכשו המג'יק אחד השחקנים הגדולים בתולדות ה-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: התחלה חדשה עם דווייט הווארד
דווייט הווארד נבחר כבחירה מספר 1 בדראפט של שנת 2004.
במהלך הפגרה, פירק וייסברוד את קבוצה לחלוטין. על אף שדייוויס שמר על מקומו כמאמן הראשי של הקבוצה, הוא המם את השחקנים כאשר החליט לשמור רק מספר מצומצם של שחקנים מהעונה שעברה בסגל הקבוצה. הטרייד המשמעותי ביותר היה זה של טרייסי מקגריידי. מקגריידי לא היה שבע רצו באורלנדו, ביקש לעבור לקבוצה אחרת; וייסברוד האשים את מקגריידי ב"התרשלות מכוונת" ובחוסר השתתפות באימונים (מאוחר יותר הודה מקגריידי כי לא נתן 100% במהלך עונת 04–2003 ורצה כי המועדון יביא לו עזרה, אך מעולם לא רצה לעזוב את אורלנדו). המג'יק העבירו את מקגריידי יחד עם ריס גיינס, טיירון לו, וג'וואן הווארד ליוסטון רוקטס בתמורה לסטיב פרנסיס, קלווין קאטו, וקוטינו מובלי, בנוסף רכשו המג'יק את הסנטר טוני באטי ושתי בחירות סיבוב שני מהקליבלנד קאבלירס בתמורה לדרו גודן, סטיבן האנטר, וזכויות הדראפט על אנדרסון וראג'ו. המג'יק החתימו גם את הידו טורקוגלו. עם בחירת הדראפט הראשונה, בחרו המג'יק את כוכב ליגת התיכוניים, דווייט הווארד והעבירו אליהם גם את הפויינט גארד ג'מיר נלסון. נלסון, שרבים מהפרשנים ציפו כי יבחר בין עשרת הראשונים בדראפט נפל לבחירה ה-20, והמג'יק העבירו לדנוור נאגטס בחירת סיבוב ראשון עתידית בתמורה.
לאחר פתיחה מבטיחה של 6–13, החלו המג'יק להתפרק. תחילה, העביר וייסברוד את מובלי לסקרמנטו קינגס תמורת דאג כריסטי. כריסטי, סירב תחילה לשחק בעבור המג'יק עקב קשריו הרגשיים לקינגס. מאוחר יותר, טען כריסטי כי הוא סובל מדורבן והוצב ברשימת הפצועים לאחר ששיחק רק משחקים בודדים בעבור המג'יק. לקראת סופה של העונה, כאשר מאמצי הפלייאוף תלויים על בלימה, פיטר וייסבורד את דייוויס לאחר שהוביל את דייוויס להאמין כי הוא אמור להישאר המאמן הראשי של הקבוצה עד לסוף עונת 05–2004. לאחר מכן, הוא קידם את כריס ג'נט לתפקיד מאמן ראשי זמני. לאורך העונה, חזרתו של היל הגביהה את רף הציפיות בקבוצה, והקבוצה שיחקה טוב למדי. המג'יק גברו במהלך העונה על קבוצות מצמרת הליגה כסן אנטוניו ספרס, דאלאס מאבריקס, מיאמי היט, פיניקס סאנס, ודטרויט פיסטונס. אך, בהתאם למסורת הבלתי יציבה של המועדון, הפסידו המג'יק גם לקבוצות בעלות מאמזן שלילי כמו קבוצת ההרחבה שארלוט הורנטס ואטלנטה הוקס. אך, הווארד הראה הבטחה גדולה, והפך לאחד השחקנים הבודדים המסיימים את העונה הסדירה עם ממוצעים של דאבל דאבל (בנקודות ובכדורים חוזרים). הווארד הפך לקולט כדורים חוזרים וספק נקודות מתמיד, הופך לרוקי הראשון בהיסטוריה של הליגה המשחק בחמישייה הפותחת בכל 82 משחקי העונה הסדירה. בנוסף, נלסון, לאחר התחלה איטית, הפך לשחקן מוכשר, תופס את עמדת הפויינט גארד הפותח של הקבוצה. היל חזר והשיג ממוצעים נאים של 19.7 נקודות למשחק. היל נבחר לחמישייה הפותחת במשחק האול סטאר של שנת 2005 על ידי האוהדים, ודווייט הווארד וג'מיר נלסון נבחרו לחמישיית הראשונה והשנייה של הרוקיז, בהתאמה, כאשר הווארד נבחר בתמימות דעים.
המג'יק סיימו את העונה במאזן 36–46, מאזן מאכזב בהשוואה לפתיחת העונה החזקה. המאמץ לבגיע אל הפלייאוף סוכל על ידי פציעות ברבע האחרון של העונה: השחקן השישי של המג'יק, הידו טורקוגלו שבר את פרק ידו לקראת סופה של העונה, פציעת שוק של היל, פציעת צלעות לנלסון, והשעייה לשלושה משחקים אותה קיבל פרנסיס לאחר שכביכול בעט בצלם. בסופה של העונה הסדירה, סיימו המג'יק בפיגור של כמה ניצחונות ממקום המוביל לפלייאוף. אך, ב-23 במאי, תוכניותיהם של המג'יק נעצרו לאחר התפטרותו הפתאומית של הג'נרל מנג'ר ג'ון וייסבורד. בנוסף, ביום למחרת הודיעה הנהלת המועדון כי בראיין היל, המאמן שהוביל את המיאמי היט, עם שאקיל אוניל ופני הארדוויי, לגמר ה-NBA, יחזור אל המועדון בתפקיד המאמן הראשי.
המג'יק בחרו את פראן ואסקס כבחירה ה-11 בדראפט של שנת 2005. ב-28 ביולי, הימם ואסקס את הקבוצה לאחר שהודיע כי הוא מעדיף להישאר בספרד כדי לשחק במדי סנט ז'וזפ ז'ירונה, לאחר שנקטל על ידי התקשורת בעקבות הידיעה כי החליט להישאר בספרד עקב התעקשותה של חברתו באותם הימים (כיום אשתו).[13] הבעלים ריצ'רד דה-ווס הודיע ב-21 באוקטובר, כי הוא מעביר את הבעלות על הקבוצה לילדיו, כאש התפקיד הרשמי של הבעלים עובר ללחותנו לנשיא המועדון בוב ונדר וייד. העברת הבעלות הייתה אמורה להסתיים עד לסיומה של העונה.
עונת 06–2005 נפתחה עם תקוות גדולות עבור המגיק, זאת על אף שלא יכלו לצרף את בחירת הסיבוב הראשון, ואסקס. גרנט היל נחשב כביכול לבריא, לראשונה מזה שמן רב, לאחר הניתוחים המורכבים אותו עבר בקרסולו הבעייתי. דווייט הווארד וג'מיר נלסון הראו התקדמות ניכרת במהלך ליגת הקיץ. קלווין קאטו הגיע בכושר למחנה האימונים. בחירת הסיבוב השני טרוויס דינר הראה יכולות קליעה משובחות ויכולת גבוהה בקבת החלטות במהלך אימוני הקיץ. והחתמת השחקן החופשי, קיון דולינג הראה ציפיות כי המועדון אליו הצטרף ימשיך להתקדם. לאחר כל תקוות אלה החלו הבעיות לצוץ, גרנט היל, אף על פי שנראה היה כי קרסולו החלים, סבל מבקע כואב ונאלץ לעבור ניתוח שפגע ביכולת המשחק שלו לאורך העונה כולה. לאחר ששיחק בשלושה משחקי קדם עונה, הוא עבר את הניתוח כדי לתקן את הבקע ולא הופיע במשחקי העונה הסדירה עד לאמצע חודש דצמבר, חזרה בה הצליח לשרוד חודש בלבד שביצע ניסיון חזרה נוסף באמצע פברואר ובתחילת מרץ, באופן לא סדיר. לאחר מכן נפצע נלסון ונאלץ לשבת חודש שלם מחוץ לקווים.
לאחר כל זה הפציעו קרני תקווה על העונה, ב-15 בפברואר הודיעו המג'יק כי הם רכשו את דארקו מיליצ'יץ' וקרלוס ארויו מהדטרויט פיסטונס תמורת הסנטר הוותיק קלווין קאטו ובחירת סיבוב ראשון בדראפט המובטחת להיות באחד מחמשת המקומות הראשונים. שבוע לאחר מכן ב-22 בפברואר הודיעו המג'יק כי הם העבירו את סטיב פרנסיס לניו יורק ניקס בתמורה לכוכבה לשעבר פני הארדוויי, המג'יק שחררו את הארדוויי יומיים לאחר מכן מטעמים כלכליים, ובתמורה לטרבור אריזה. עם חמישייה פותחת שכללה את באטי, הווארד, טורקוגלו, ד'שון סטיבנסון, ונלסון, הצליחו המג'יק להפתיע ולהתחרות על המקום השמיני במזרח ולהגיע למשחקי הפלייאוף, הריצה לפלייאוף של המג'יק כללה שמונה ניצחונות רצופים ושנים עשר ניצחונות ביתיים רצופם. המג'יק הצליחו לנצח כמה מהקבוצות הגדולות של הליגה וביניהם: דטרויט, סן אנטוניו, מיאמי, כמו גם במשחקים נגד הפילדלפיה 76' בו קלע הווארד 28 נקודות והשיג שיא קריירה של 26 ריבאונדים. ניצחונם של השיקגו בולס על המיאמי היט ב-16 באפריל חיסל את סיכוייהם של המג'יק למקום בפלייאוף, הבולס גם סיימו את רצף הניצחונות של המג'יק כאשר גברו עליהם ב-17 באפריל, באורלנדו 112–116 לאחר הארכה.
2006-2010: חזרה לפלייאוף ולגמר ה-NBA
עם הבחירה ה-11 בדראפט בחרו המג'יק את כוכבה של דיוקג'יי. ג'יי. רדיק, גם עם לחצם של האוהדים שיקבל יותר דקות משחק, הוא שיחק בממוצע 11 דקות בלבד למשחק. לאחר שהחלו את העונה בצורה חזקה והגיעו למאזן של 4–13, החלו המג'יק להדרדר במיקומם בטבלה לאחר ההחלו לצבור הפסדים, בעיקר עקב פציעתם של טוני באטי, קיון דולינג, וגרנט היל. המג'יק גם נפגעו עקב משחקם המפוזר של כוכביהם הצעירים, שבהזדמנויות רבות הראו את יכולותיהם וזיקתם לזריקות מיותרות ואת חסרונו של גארד שני יציב. למרות משחקה העלוב של הקבוצה, דווייט הווארד המשיך להתפתח ולפרוח בעונתו השלשית בליגה, כשהוא מגיע לשיאו בבחירתו לנבחרת המזר למשחק האול סטאר. בשבועות האחרונים של העונה בנו המג'יק מומנטום וביטחון בדחיפה מאוחרת ומרשימה אל עבר הפלייאוף. ב-15 באפריל 2007, לאחר ניצחון 86–88 על הבוסטון סלטיקס, הצליחו המג'יק להבטיח את הופעתם בפלייאוף לראשונה מאז שנת 2003 כשהם מסיימים במקום השמיני במזרח. סיומה של העונה הסדירה ציין את הפעם הראשונה בה מצליח המועדון להעפיל אל משחקי הפלייאוף עם מאזן שלילי. למרות כל זאת, ריצת הפלייאוף של המג'יק הסתיימה ב-28 באפריל 2007, לאחר שהודחו ב"סוויפ" בסיבוב הראשון בידי המדורגת ראשונה דטרויט פיסטונס, שחוותה, סגל שחקנים המונהג בידי שחקנים מנוסים, יכולת טובה יותר, והציגה עקביות לאורך כל הסדרה. דבר שהוכח כיותר מידי עבור המג'יק ההמומים ובעלי הסגל השחקנים הקצר. ב-23 באפריל 2007, נודע כי המאמן הראשי בראיין היל פוטר מתפקידו.
ב-1 ביוני, החתימו הנהלת אורלנדו את המאמן בילי דונובן לתפקיד המאמן הראשי בחוזה לחמש שנים. יום למחרת, ביקש דונובן להשתחרר מהחוזה והמג'יק קיבלו את רצונו כמה ימים לאחר מכן. ב-6 ביוני 2007, החתימה הנהלת אורלנדו את סטן ואן גנדי על חוזה לארבע שנים כמאמן הראשי החדש של המג'יק. בשוק השחקנים החופשיים, החתימו המג'יק את רשארד לואיס מהסיאטל סופרסוניקס על חוזה מקסימום לשש שנים ששוויו הוערך ב-110 מיליון דולר.[14] במשחקי פתיחת העונה ששוחקו בסין, נצחו המג'יק את כל שלושת המשחקים, פעמיים את הקליבלנד קאבלירס ופעם אחת את הנבחרת הלאומית של סין במשחקים שנערכו בשאנגחאי ובמקאו.
ב-15 בנובמבר 2007 בוב ונדר וייד, חותנו של ריצ'רד דהווס, העביר לידיו בצורה רשמית את הבעלות על המועדון, על אף שרשמית הבעלות על המועדון מתחלק בצורה שווה בין כל ילדיו.
את עונת 08–2007 פתחו המג'יק בצורה מוחצת והשיגו מאזן של 4–16 ב-20 המשחקים הראשונים של העונה, שכללו ניצחונות על הבוסטון סלטיקס, והקליבלנד קאבלירס. בחודשים שבאו לאחר מכן, המג'יק לא הצליחו להשיג את אותה ההצלחה, כשהם מחלקים את 36 המשחקים הבאים שלהם בצורה שווה 18-18. בתחילת חודש מרץ, נראה היה כי המג'יק מצליחים לצבור שוב מומנטום, כשהם מסיימים את החודש עם 10 ניצחונות, הפעם הראשונה מאז חודש נובמבר בה הם מצליחים לנצח יותר מ-10 משחקים ויותר בחודש אחד. המג'יק חבקו את תואר האליפות של הבית הדרום-מזרחי לאחר שב-31 במרץ 2008, הוושינגטון ויזארדס הובסו ביוטה 87–129. היה זה תואר אליפות בית השלישית בתולדות המועדון, אך הראשון מאז עונת 96–1995, כמו גם הראשונה מאז הקמת הבית הדרום-מזרחי. המג'יק גם הצליחו להגיע ל-50 ניצחונות לאחר שגברו, ב-13 באפריל, על השיקגו בולס, הישג שלא קרה מאז עונת 96–1995. המג'יק סיימו את העונה הסדירה במאזן של 30–52, העונה הטובה ביותר של המועדון מאז עונת 96–1995. והצליחו להשיג את המקום השלישי בפלייאוף המזרח, המג'יק נקבעו לשחק מול הטורונטו ראפטורס בסיבוב הראשון של הפלייאוף. סדרת פלייאוף זו הייתה הראשונה בה היה למג'יק יתרון ביתיות מאז עונת 99–1998.
ב-28 באפריל 2008, באמוויי ארנה, הדיחו המג'יק את הראפטורס עם ניצחון 1–4 בסיבוב הראשון של הפלייאוף. היה זה הניצחון הראשון בסדרת פלייאוף עבור המג'יק מזה 12 שנה לאחר 6 פעמים רצופות בהם הודחו המג'יק בסיבוב הראשון. אך ההצלחה לא המשיכה והאירה פנים למג'יק לאחר שהפסידו בסיבוב השני 1–4 לדטרויט פיסטונס המנוסים בסיבוב השני. כאשר המג'יק כבר נמצאים בפיגור בסדה נגד הפיסטונס, מחלוקת פרצה סביב ניצחונה של דטרויט במשחק מספר 2. לקראת סיומו של הרבע השלישי, קלע כוכב דטרויט צ'אנסי בילאפס סל 3 נקודות שהעלה את הפיסטונס ליתרון 3 נקודות. אך, שעון השניות עצר בדיוק כאשר החל המהלך שהוביל לסל היתרון. חוקי ליגת ה-NBA אוסרים על שימוש מיידי בהילוכים חוזרים או כל מכשיר למדידת זמן כדי לקבוע כמה זמן חלף מאז עצר שעון השניות. הנהלת הליגה הודתה לאחר מכן כי המהלך ערך 5.7 שניות וכי סל המחלוקת לא היה צריך להיות מאושר.[15] הפיסטונס המשיכו ונצחו במשחק השני. המג'יק הצליחו לנצח במשחק השלישי, כאשר כוכב הפיסטונס בילאפס נעדר ברוב דקות המשחק עקב פציעה, אך המג'יק לא הצליחו לנצל את היתרון מהעדרו ונוצחו על ידי הפיסטונס בשני המשחקים הבאים והודחו ממשחקי הפלייאוף של שנת 2008.
המחצית הראשונה של עונת 09–2008 הייתה מוצלחת מאוד עבור המג'יק. לאחר 41 משחקים, היו המג'יק במאזן של 8–33, והובילו את הבית הדרום-מזרחי, כמו גם החזיקו באחד מארבעת המאזנים הטובים ביותר בליגה כולה. בתחילת חודש פברואר, ג'מיר נלסון, הפויינט גארד הפותח של המג'יק ושחקן אול סטאר, נאלץ לשבת ביציע לאחר פציעת כתף. ההערכה הייתה כי הוא יאלץ להחמיץ את שארית העונה. כדי למלא את החלל שנוצר מהעדרו הביאו המג'יק בטרייד את רייפר אלסטון מהיוסטון רוקטס, המג'יק סיימו את העונה במאזן 23–59, הייתה זו כמות הניצחונות לעונה השנייה בטיבה בכל הזמנים מאז עונת 96–1995, אז נצחו המג'יק 60 משחקים. בפלייאוף, גברו המג'יק על הפילדלפיה 76' בסיבוב הראשון של הפלייאוף ובחצי גמר המזרח גברו על האלופה המכהנת הבוסטון סלטיקס, עומדים בהבטחתו של עוזר המאמן פטריק יואינג על כך שהקבוצה תנצח במשחק השביעי והמכריע.[16] בגמר האזורי הראשון מאז שנת 1996, גברו המג'יק על הקליבלנד קאבלירס, בהנהגתו של ה-MVP של העונה הסדירה, לברון ג'יימס. לאחר שנוצחו בשני המשחקים הראשונים בגמר ה-NBA נגד הלוס אנג'לס לייקרס, הצליחו המג'יק לנצח במשחק הראשון בגמר ה-NBA בתולדות המועדון, משחק מספר 3. למרות חזרתו של נלסון לסגל סדרת הגמר, גברה הלוס אנג'לס לייקרס על האורלנדו מג'יק בחמישה משחקים וזכתה באליפות ה-NBA.
בפגרת שנת 2009, העבירו המג'יק את רייפר אלסטון, טוני באטי, וקורטני לי, לניו ג'רזי נטס תמורת וינס קרטר, קרטר יליד פלורידה, הופיע שמונה פעמים במשחק האול סטאר וראיין אנדרסון.[17]הידו טורקוגלו כחלק מעסקת החתם והשאל, נשלח לטורונטו ראפטור. לאחר מכן החתימו המג'יק כמה שחקנים חופשיים. ב-10 ביולי, שחקנה לשעבר של הדאלאס מאבריקס ברנדון באס קיבל חוזה ל-4 שנים.[18] ב-21 ביולי, החתימו המג'יק את שחקנה לשעבר של הפיניקס סאנסמאט בארנס.[19] ב-19 באוגוסט, הם החתימו את שחקנה לשעבר שהמיאמי היט הפויינט גארד ג'ייסון ויליאמס.[20]
ב-28 בספטמבר 2009, האריכו המג'יק את חוזהו של המאמן ואן גנדי, כשהם מנצלים את האופציה לכך בחוזה ביניהם, לעונת 11–2010. הם עשו את אותו הדבר גם עם הג'נרל מנג'ר אוטיס סמית', שישאיר אותו בתפקיד זה גם בעונת 2011-12.[21]
בעשרה המשחקים הראשונים של עונת 10–2009 נעדר רשארד לואיס. תוצאות בדיקת סמים שערך לואיס נמצאו חיוביות, כאשר בגופו נמצא עודף טסטוסטרון הנובע מכך שקיבל תוסף תזונה "מתחת לשולחן" הכיל ממריצים האסורים על פי הליגה.[22] וכי להחמיר את מצבה של הקבוצה, וינס קרטר נפצע בקרסולו השמאלי כבר במשחק השני של העונה. פציעתו של קרטר התבררה כאינה חמורה מידי, אך גרמה לו להחמיץ את חמשת המשחקים הבאים של הקבוצה. עוד עיכוב בהתקדמותה של הקבוצה ארעה באמצע חודש נובמבר, כאשר ג'מיר נלסון נפצע בברכו השמאלית, שדרשה התערבות כירורגית כדי לתקנה. נלסון נעדר לחמשת השבועות הבאים. למרות כל זאת, הצליחו המג'יק להגיע למאזן של 8–23 בסוף חודש דצמבר.
המג'יק הפסידו בשבעה מעשרת המשחקים הראשונים שלהם בחודש ינואר, אך הצליחו להתאושש ולסיים את החודש במאזן חיובי לאחר שנצחו ששת משבעת המשחקים האחרונים של החודש. לאחר פגרת האול סטאר, הצליחו המג'יק להיכנס לתלם, כאשר נצחו 23 מ-28 המשחקים הנותרים לעונה, כשהם מתברגים להופעת פלייאוף עונה רביעית ברציפות וזוכים בפעם השלישית ברציפות באליפות הבית ה-דרום-מזרחי. המג'יק סיימו את העונה הסדירה במאזן 23–59, משווים את שיאם מעונת 09–2008, ומסיימים לא רק עם המאזן השני בטיבו במזרח, אלא עם המאזן השני בטיבו בליגה כולה. המג'ק גברו בסוויפ על השארלוט בובקאטס ועל האטלנטה הוקס בשני הסיבובים הראשונים של הפלייאוף, בהתאמה. לאחר מכן, נפגשו המג'יק עם הבוסטון סלטיקס בגמר המזרח. לאחר שנוצחו בשלושת המשחקים הראשונים, הצליחו המג'יק לנצח בשני המשחקים הבאים, אך הפסד חוץ במשחק השישי, סיים עבורם את העונה.
2010-הווה: אולם חדש, מראה חדש
בציפייה למעברה של הקבוצה לאולם החדש, אמוויי ארנה, עדכנו המג'יק את סמל הקבוצה. הם השאירו את הכדור אך שינו את צורת הכתב כך שיתאים לצורת הכיתוב על המדים. המג'יק אמורים לארח את סוף שבוע האול סטאר של שנת 2012. בנוסף שינה המועדון את המדים החלופיים של המועדון לשחור.
בקיץ שנת 2010 החתימו המג'יק את כריס דוהון, שחקנה לשעבר של הניו יורק ניקס,[23] וקוונטין ריצ'רדסון, שחקנה לשעבר של המיאמי היט.
המג'יק סיימו את העונה הסדירה עם 52 ניצחונות, שהציבו אותם במקום השני בבית הדרום-מזרחי. אך הופתעו ונוצחו בידי האטלנטה הוקס בשישה משחקים, בסיבוב הראשון של פלייאוף 2011, הייתה זו הפעם הראשונה בה המאמן סטן ואן גנדי הודח בסיבוב הראשון של הפלייאוף.
בעונת 12–2011 אורלנדו סיימה במקום השישי במזרח והפסידה לאינדיאנה בסיבוב הראשון בחמישה משחקים בלי הווארד הפצוע שחתם על חוזה לעוד עונה.
אולמות ביתיים
במקור כונה אורלנדו ארנה, ומאוחר יותר TD ווטרהאוס סנטר, האמווי ארנה היה ביתם של האורלנדו מג'יק בין השנים 1989–2010
אמווי ארנה (אולם לשעבר)
האמווי ארנה נפתח בשנת 1989 ושימש כאולם הביתי של המג'יק מתחילת דרכם בליגת ה-NBA ועד לסוף עונת 10–2009. במקור הוא נודע בשם האורלנדו ארנה, במהלך העשר שנים הראשונות. בשנת 1999, TD ווטרהאוס רכשו את הזכויות על שם האולם ושינו את השם ל-TD ווטרהאוס סנטר. בדצמבר 2006, נרכשו הזכויות לשם בידי חברת אמוויי לארבע שנים. האולם גם שימש כאולם הביתי של האורלנדו פרדטורס והאורלנדו שארקס מליגת כדורגל האולמות, כמו כן לכמה אירועי ספורט ובידור.
