המג'יק בחרו את פראן ואסקס כבחירה ה-11 בדראפט של שנת 2005. ב-28 ביולי, הימם ואסקס את הקבוצה לאחר שהודיע כי הוא מעדיף להישאר בספרד כדי לשחק במדי סנט ז'וזפ ז'ירונה, לאחר שנקטל על ידי התקשורת בעקבות הידיעה כי החליט להישאר בספרד עקב התעקשותה של חברתו באותם הימים (כיום אשתו). הבעלים ריצ'רד דה-ווס הודיע ב-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 מיליון דולר. במשחקי פתיחת העונה ששוחקו בסין, נצחו המג'יק את כל שלושת המשחקים, פעמיים את הקליבלנד קאבלירס ופעם אחת את הנבחרת הלאומית של סין במשחקים שנערכו בשאנגחאי ובמקאו.
ב-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 שניות וכי סל המחלוקת לא היה צריך להיות מאושר. הפיסטונס המשיכו ונצחו במשחק השני. המג'יק הצליחו לנצח במשחק השלישי, כאשר כוכב הפיסטונס בילאפס נעדר ברוב דקות המשחק עקב פציעה, אך המג'יק לא הצליחו לנצל את היתרון מהעדרו ונוצחו על ידי הפיסטונס בשני המשחקים הבאים והודחו ממשחקי הפלייאוף של שנת 2008.
המחצית הראשונה של עונת 09–2008 הייתה מוצלחת מאוד עבור המג'יק. לאחר 41 משחקים, היו המג'יק במאזן של 8–33, והובילו את הבית הדרום-מזרחי, כמו גם החזיקו באחד מארבעת המאזנים הטובים ביותר בליגה כולה. בתחילת חודש פברואר, ג'מיר נלסון, הפויינט גארד הפותח של המג'יק ושחקן אול סטאר, נאלץ לשבת ביציע לאחר פציעת כתף. ההערכה הייתה כי הוא יאלץ להחמיץ את שארית העונה. כדי למלא את החלל שנוצר מהעדרו הביאו המג'יק בטרייד את רייפר אלסטון מהיוסטון רוקטס, המג'יק סיימו את העונה במאזן 23–59, הייתה זו כמות הניצחונות לעונה השנייה בטיבה בכל הזמנים מאז עונת 96–1995, אז נצחו המג'יק 60 משחקים. בפלייאוף, גברו המג'יק על הפילדלפיה 76' בסיבוב הראשון של הפלייאוף ובחצי גמר המזרח גברו על האלופה המכהנת הבוסטון סלטיקס, עומדים בהבטחתו של עוזר המאמן פטריק יואינג על כך שהקבוצה תנצח במשחק השביעי והמכריע. בגמר האזורי הראשון מאז שנת 1996, גברו המג'יק על הקליבלנד קאבלירס, בהנהגתו של ה-MVP של העונה הסדירה, לברון ג'יימס. לאחר שנוצחו בשני המשחקים הראשונים בגמר ה-NBA נגד הלוס אנג'לס לייקרס, הצליחו המג'יק לנצח במשחק הראשון בגמר ה-NBA בתולדות המועדון, משחק מספר 3. למרות חזרתו של נלסון לסגל סדרת הגמר, גברה הלוס אנג'לס לייקרס על האורלנדו מג'יק בחמישה משחקים וזכתה באליפות ה-NBA.