1986-1992：艱難的起步時期
1986-89：魔術的誕生
奧蘭多本地的開發商及銀行家吉姆-休伊特(Jim Hewitt)花了將近四年的時間為他的家鄉帶來了一支NBA球隊：他將當時76人的總經理帕特-威廉士(Pat Williams)挖到了佛羅里達，後者就職後鏇即開始負責銷售印有奧蘭多魔術字樣的T恤、球帽以及其他商品——甚至勸說當地民眾以100美元的價格來預定未來的季票。
他們的努力沒有白費，生活在佛羅里達中部的籃球迷們所表現出的極大的熱情打動了NBA。1986年7月2日，休伊特代表的魔術隊支付了10萬美元成為5個NBA擴軍候選球隊之一。幾乎就在一年之後，1987年4月22日，NBA董事會正式投票通過了其中四支球隊的加入請求：1988-1989賽季夏洛特黃蜂隊和邁阿密熱火隊首先進入聯盟，而奧蘭多魔術隊與明尼蘇達森林狼隊在隨後的一個賽季，也就是1989-1990賽季加入，這四支球隊必須分別支付3250萬美元的加盟許可費。
1989-90： 76人舊將領導下的魔術
威廉馬斯選擇了馬特-古科斯(Matt Guokas)作為球隊的第一任主教練。古科斯在1966至1976的十年間曾經作為球員為6支不同的球隊效力過。他在76人隊度過了自己職業生涯最初的四個半賽季——這也是古科斯效力時間最長的球隊。從某種意義上講，古科斯是幸運的：他在其新秀賽季就作為球隊的替補後衛拿到了無數人望穿秋水卻得之不得的總冠軍戒指。退役後，古科斯成為76人隊主場的廣播員，隨後又作為比利-坎寧安(Billy Cunningham)的助手在1983再次隨隊拿到了總冠軍。在1984-85賽季比利-坎寧安辭職後，古科斯正式成為了費城76人隊的主教練。然而僅過了兩個半賽季，他的位置就被吉姆-萊納姆(Jim Lynam)於1987-88賽季中期取代。
魔術隊在1989年的擴軍選秀中一共挑選了12名球員，其中包括雷吉-希厄斯(Reggie Theus)，斯科特-斯凱爾斯(Scott Skiles)，特里-卡特萊奇(Terry Catledge)，薩姆-文森特(Sam Vincent)，奧蒂斯-史密斯(Otis Smith)和傑里-雷諾茲(Jerry Reynolds)。隨後，他們在正式的NBA選秀中利用手中的11順位挑選了伊力諾依大學的鋒衛搖擺人尼克-安德森(Nick Anderson)。
作為NBA新軍，魔術隊的處子賽季一開始並沒有像人們預料的那樣缺乏人氣。1989年11月4日，在觀眾爆滿的奧蘭多體育館裡，魔術隊開始了他在NBA的第一場比賽。特里-卡特萊奇，傑里-雷諾茲，戴夫-科爾津(Dave Corzine)，雷吉-希厄斯，和薩姆-文森特組成了魔術隊史上的第一個先發陣容。雖然擁有5年NBA球齡的前鋒卡特萊奇在本場比賽表現出色，一個人拿下了球隊史上的第一個兩雙(25分16個籃板)，但是魔術隊還是以106-111的比分輸給了客場作戰的新澤西網隊。
然而僅僅兩天之後，魔術就獲得了他們隊史上的第一場勝利，被記在檔案中的另一支球隊名叫紐約尼克斯……118比110，希厄斯貢獻了全隊最高的24分。又過了兩天，克里夫蘭的球迷就目睹了魔術隊的首次連勝——他們的球隊主場110-117輸給了來訪的NBA新軍。當賽季的頭一個月過去時，魔術隊以7勝7負的成績創造了NBA新軍開賽的最好記錄。
但是，好花不常開，好運不常在。也許是出色的開局花掉了魔術隊太多的運氣。在隨後的比賽里，魔術隊僅取得了11勝57負的成績……就整個賽季而言，球隊的成績並不十分理想。但是，在這個負多勝少的賽季里，魔術隊中的許多隊員卻有著讓人印象深刻的出色發揮：卡特萊奇在與金洲勇士的比賽中砍下了49分；文森特在戰勝印第安那步行者的比賽里拿到了球隊史上的第一個三雙(27分17次助攻11個籃板)，而且在1990年1月，他的12年職業生涯即將結束的時候還連續在罰球線上投中了50球；麥可-安斯利(Michael Ansley)更是在2月1日客場對陣雄鹿時搶到了13個進攻籃板，創造了球隊以及NBA的單季紀錄。
魔術隊在處子賽季就成為了聯盟中進攻火力最強大的隊伍之一(場均得到110.9位列第五),但是他們糟糕的防守(場均失分119.8聯盟墊底)拖了他們的後腿，這直接導致了18勝64負的戰績出爐。而與他們同時進入聯盟的明尼蘇達森林狼的戰績是22勝60負。不過萬幸的是，魔術隊本賽季三勝新澤西網隊使得他們不用在聯盟墊底——被他們三次戰勝的網隊以17勝65負的成績當上了副班長。
球隊的戰績不佳並沒有影響球迷的熱情，奧蘭多主場的球票連續33場銷售一空，整個賽季平均上座率達到一萬五千人。特里-卡特萊奇 (場均19.4 分) 和 雷吉-希厄斯 (18.9分)在球隊得分榜上領跑，另外五名球員薩姆-文森特，傑里-雷諾茲，尼克-安德森，奧蒂斯-史密斯，和 希德尼-格林(Sidney Green)的場均得分也都上了兩位數。籃板方面，格林以8.1個籃板領先全隊，卡特萊奇則以7.6個緊隨其後。
1990-92：奧蘭多得到神射手斯科特
魔術隊在1990年的選秀大會上用四號簽挑選了喬治亞理工的神投手丹尼斯-斯科特(Dennis Scott)。斯科特身高6尺8，司職小前鋒，大學三年級時已經能夠每場拿下27.7分，三分命中率為41.4%。他的到來進一步加強了魔術隊的攻擊火力。
在這個賽季里，魔術隊取得了相當顯著的進步，與上賽季相比勝率提高了將近一倍(31勝51負)。雖然開局並不是很好，但是隨著賽季的進行，球隊漸漸打出了古科斯教練所要希望的籃球。在二月魔術隊取得了8勝3負的好成績——這是球隊首次在一個月內勝率超過50%——而賽季最後的三個月里球隊的總戰績也達到了20勝18負。
在經歷了開賽六連敗以及到一月為止的11勝33負後，球隊的打法開始向團隊籃球的方向轉變並且取得了很好的效果。12月30日，魔術隊一位身高6尺1寸的球員在與掘金隊的比賽中創造了隊史上的第一個NBA歷史紀錄——單場30次助攻。而這位隊員就是目前芝加哥公牛隊的主教練斯科特-斯凱爾斯。截止到二月底，魔術隊已經成功超越了上賽季的獲勝場次。在賽季的最後一場比賽里，魔術隊漂亮的以120-110擊敗了籃網，拿到了第31場勝利，而這也使得球隊成為NBA該賽季進步最快的隊伍。
在球員方面：斯凱爾斯打出了他職業生涯最出色的一個賽季，得到全隊最高的17.2分以及8.4個助攻，並在賽季結束時得到了NBA進步最快球員獎；新秀丹尼斯-斯科特也不負眾望，在3月8日與掘金隊的比賽中拿到了球隊賽季的最高分——40分，並且創造了單賽季投進125個三分的球隊以及NBA新秀紀錄，理所應當的進入了年度新秀第一陣容。而且由於充分貫徹了團隊進攻的理念，球隊還有另外五人場均得分在12.9以上。上個賽季糟糕的防守也大有改觀(場均失分109.9)，比起處子賽季來整整少丟了10分。球隊戰績大幅提高自然是在情理之中。
然而，接下來的一個賽季卻是令人失望的。魔術隊的戰績僅為21勝61負，而且沒有一個月的勝率超過50%(與球場上糟糕的成績相反，奧蘭多主場依然場場爆滿)。傷病是戰績下滑的一個重要原因，球隊主力斯科特因傷只出戰了18場比賽，尼克-安德森也曾經22場連續作壁上觀。其實，在91-92賽季剛開始的時候，魔術隊的表現還是可圈可點的：安德森在對華盛頓子彈隊的比賽里創下了球隊的單場搶斷紀錄(8個)。在同一個月，特里-卡特萊奇也曾經一場比賽抓下22個籃板，但不幸的是，魔術隊在還算不錯的開局後經歷了一個漫長的17連敗(其中十月的15戰全負)。繼而，正所謂兵敗如山倒：人們還能記住的球隊最後一次爆發是一月八號客場對陣超音速的比賽——薩姆-文森特拿下了35分幫助球隊以104-103一分險勝。
在球員方面，安德森在出賽的60場比賽里場均送出19.9分，而斯科特在僅有的18次出場裡也能平均拿下19.9分。卡特萊奇與斯凱爾斯則分別成為球隊的籃板王(7.0)與助攻王(7.3)。總體來說，雖然球隊戰績糟糕，但是這些角色球員穩定的成長為日後那一天的到來打下了良好的基礎。
1992-1996：奧尼爾帶來巨大成功
1992-93：球隊史上最重要的一天
1992年5月17號，經歷了一個令人失望的賽季後球隊終於得到了相應的(後來看起來應該是超值的)安慰——他們贏得了1992年度聯盟選秀的狀元簽。隨後不出意外地，魔術隊在92年的選秀大會上選擇了來自路易斯安娜州身高7尺1，體重301磅的天才中鋒沙奎爾-奧尼爾。
自從“沙克”加進球隊後，每件事情似乎都開始向著好的方向發展。丹尼斯-斯科特，特里-卡特萊奇，斯科特-斯凱爾斯，尼克-安德森與代替格雷格-凱特(Greg Kite)出任首發中鋒的沙奎爾-奧尼爾組成了球隊新的首發陣容。要不是斯科特與內線替補布萊恩-威廉士(Brian Williams)的因傷缺陣(分別為24場與61場)，球隊本來應該對聯盟造成更大的衝擊——即使這樣，到賽季結束時人們也驚喜地發現魔術隊的戰績比起上賽季時提升了整整二十場，成為當賽季聯盟進步最快球隊。
而奧尼爾，以他魁梧的身材，閃亮的光頭和開朗的笑容迅速成為籃球運動最有代表力的人物之一——也許僅僅位列於芝加哥公牛的“飛人”麥可-喬丹(Michael Jordan)之後。2月21號，奧尼爾作為繼喬丹之後第一位被選入全明星先發陣容的菜鳥參加了鹽湖城的全明星周末活動。
3月27號，球隊贏得了之前三個賽季從未贏到過的第32場比賽。而奧尼爾也並不是唯一一位創造歷史的功臣，丹尼斯-斯科特在4月對陣雄鹿的比賽中也投中了球隊單場紀錄的9個三分球——僅僅比邁阿密的布萊恩-肖(Brian Shaw)在一周前創造的NBA單場紀錄少一個。
當然，斯科特的三分雨並不能掩蓋奧尼爾的光芒，在斯科特的掃射下奧尼爾也拿下了15分16個籃板使他成為繼巴克-威廉士(Buck Williams)之後第一位在一個賽季內拿下1000分及1000個籃板的菜鳥。
三天后，第一節將板凳坐穿的尼克-安德森在後三節里25投17中，並在罰球線上12罰全中，單場送給網隊50分，一舉打破特里-卡特萊奇保持的球隊紀錄。
最終，奧蘭多用一場對老鷹的勝利結束了這個最成功的賽季(位列大西洋賽區第四位)，卻遺憾地被印第安那擠出了季候賽。球隊糟糕的客場成績是無緣季後賽的主要因素，14勝27負的客場戰績與27勝14負的主場戰績形成截然反差。
但是，無論如何，一支有著光明未來的球隊雛形已然形成了：
球隊得分王奧尼爾場均砍下23.4分，總分1893分以及56.2%的命中率都是球隊的新紀錄(當然還有不可忽略的場均13.9個籃板與3.53次封蓋)。他是聯盟中唯一一位在得分(第8)，籃板(第2)，封蓋(第2)和命中率(第4)都排入前十的球員——雖然許多觀察家認為奧尼爾的技術還相當粗糙，在場上基本上都的是靠他那恐怖的身體來統治內線。但是無論專家如何評論，作為一名明星，奧尼爾已經是很難有人能夠匹敵了：在短短的一年裡，他出現在球鞋和飲料的廣告中，推出一張名為沙克柴油機(Shaq Diesel)的說唱樂唱片，並在一部名為《火爆教頭》(BLUE Chips)的大學籃球題材影片中客串。
角色球員方面：尼克-安德森成為奧尼爾的好幫手，場均得到19.9分並且幾乎所有的技術統計都為職業生涯新高。丹尼斯-斯科特和斯科特-斯凱爾斯也有場均15+的得分。斯凱爾斯仍然是高效的組織者，一個賽季下來送出了職業生涯最高的735次助攻(場均9.4次，聯盟第三)。
賽季結束後，球隊的主教練馬特-古科斯的職位被原助理教練布萊恩-希爾(Brian Hill)頂替。後者有著24年的高中、大學以及職業執教經驗，並且深受隊中球員的歡迎。
在錯過1993年的季候賽之後，魔術隊作為未進季後賽的球隊中戰績最好的一支(當然也就是獲得狀元秀機率最低的球隊：66分之1)參加了當年的選秀抽籤大會。不可思議的是，球隊再次獲得了狀元簽！回顧歷史，上一次連續兩年拿到狀元簽的球隊是休斯敦火箭，他們用1983與84連續兩屆的第一選秀權選擇了拉爾夫-桑普森(Ralph Sampson)和哈基姆-奧拉朱旺(Olajuwon)。
1993-94：一枚價值百萬的“便士”
在選秀大會上，奧蘭多魔術隊利用手上的第一選秀權完成了近年來最大的一筆選秀當日交易：當時密西根大學的克里斯-韋伯(Chris Webber)是當時公認的狀元不二人選，然而已經擁有奧尼爾的魔術隊卻對來自孟菲斯的後衛“便士”安芬尼-哈達威(Anfernee “Penny” Hardaway)更感興趣。根據當時情況分析，擁有三號選秀權的金州極有可能挑選哈達威，因此魔術選中韋伯後馬上與選中哈達威的勇士隊進行了交易。就這樣，便士與三個未來的首輪選秀權打包來到了魔術隊。
1993年選秀大會上發生的這筆交易確保了魔術隊在接下來的幾個賽季中擁有足夠的競爭力：他們不但擁有了年輕而又富有潛力的前後場兩人組合(奧尼爾和哈達威)，還在未來的七年中擁有十一個首輪選秀權。
在接下來的93-94賽季中，魔術隊意料之中地爆發了。球隊不但以50勝的成績闖入季後賽，沙奎爾-奧尼爾和安芬尼-哈達威的存在更是使魔術成為職業運動領域中最有吸引力的球隊之一。
在賽季伊始，哈達威被教練安排在了得分後衛的位置上，與老將斯凱爾斯聯手組成魔術的後場。但到了賽季中期，哈達威終於打回了自己最熟悉的1號位，斯凱爾斯退居二線，尼克-安德森移回後衛線與哈達威搭檔。在菜鳥賽季里，哈達威平均每場得到16.6分，6.6次助攻，5.4個籃板以及排名聯盟第六的2.32 次搶斷，毫無懸念的入選年度新秀一隊，在最佳新秀的評比中也僅以毫釐之差輸給了當年的狀元克里斯-韋伯。
新人哈達威的確表現出色，但是球隊真正的基石還是當家中鋒奧尼爾。儘管賽季初有一些人批評這位7尺1寸的怪物中鋒在休戰期花費了太多時間去拍電影和灌唱片，忽略了磨練自己的進攻技巧。但是在常規賽結束後，奧尼爾用場均29.3的得分擊碎了這些評論——如果不是馬刺隊的大衛-羅賓遜(David Robinson)在最後一場比賽中瘋狂砍下71分，奧尼爾極有可能成為本賽季的得分王。與此同時他有著領先聯盟的命中率(59.9%)，第二的場均籃板(13.2)和第六的場均封蓋(2.9)，並連續第二年被選為全明星首發。
本賽季魔術隊在全明星賽前27勝20負，全明星周末結束後23勝12負，最終以大西洋分區第二的身份挺進季後賽，但是在首輪便倒在了當年的季後賽黑馬步行者腳下——後者則一直殺入了東區決賽。賽季結束後，奧尼爾跟隨美國夢之二隊拿下了1994世界籃球錦標賽的金牌。
1994-95：東部的野獸
僅僅在建隊的第六個賽季，奧蘭多魔術球隊便以57勝25負的戰績成為了東部的老大，並且在季後賽里一路擊敗波士頓凱爾特人、芝加哥公牛以及印第安那步行者昂首闖入總決賽。
儘管首次踏上總決賽賽場的魔術隊最終被經驗豐富的衛冕冠軍休斯敦火箭以4-0的總比分擊敗，但是這支年輕、富有朝氣的球隊通過常規賽季以及直至總決賽前穩定且強硬的表現證明了自己即將成為NBA未來幾年中的一股主流力量。
沙奎爾-奧尼爾與安芬尼-"便士" 哈達威組成了魔術隊才華橫溢、令人羨慕的雙人核心。 奧尼爾在他職業生涯的第三年終於拿下了NBA常規賽季的得分王(29.3)，另外他還有著排名聯盟第三的籃板(11.4)、第二的命中率(58.3%)以及第六的封蓋(2.43)，最終入選NBA第二最佳陣容。
在總決賽里，奧尼爾與經驗豐富的明星中鋒哈基姆-奧拉朱旺(Hakeem Olajuwon)戰得不分軒桎，而後者剛剛在西部分區決賽中擊敗了馬刺的常規賽MVP得主大衛-羅賓遜，並最終得到了總決賽的MVP。
度過菜鳥賽季的哈達威也在NBA的超級球星名單里添上了自己的名字。他平均每場拿下20.9分和7.2次助攻，與奧尼爾一樣作為全明星首發的他最終入選NBA最佳陣容一隊。在四場總決賽里，哈達威場均以50%的命中率拿下25.5分和8.0次助攻，並且三分命中率也高達45.8%。
雖然兩位年輕的超級巨星是魔術隊成功的基石，但是霍雷斯-格蘭特(Horace Grant)的加入也是魔術隊1994-95賽季成功的關鍵要素之一。這位全明星前鋒帶著三枚總冠軍戒指在賽季開始前以自由人的身份加入了魔術隊。
他不僅為球隊帶來了每場9.7個籃板和12.8分(56.7%的命中率)，更重要的是他那強烈的求勝欲望、堅韌的球風、豐富的場上經驗以及影響力正是年輕的魔術隊所急需的。在賽季結束時，格蘭特也連續第三年入選NBA最佳防守二隊。
1995-96：受到威脅的魔術
95-96賽季，由沙奎爾-奧尼爾，霍雷斯-格蘭特，尼克-安德森，丹尼斯-斯科特和安芬尼-哈達威組成先發五虎的魔術隊用出色的戰績證明了上賽季打入總決賽絕非僥倖——奧蘭多的這支球隊確實已經步入NBA頂級球隊的行列。
奧蘭多在常規賽里秋風掃落葉般的拿下了60個勝場，毫無爭議地蟬聯大西洋分區冠軍。但就整個東部聯盟而言，當年最風光的球隊無疑是傳奇球星麥可-喬丹回歸以及籃板王丹尼斯-羅德曼(Dennis Rodman)加盟的芝加哥公牛隊，他們在82場常規賽中取得了不可思議的72勝10負的戰績——當常規賽季結束時，幾乎一切跡象都表明這兩支球隊將在東部7戰4勝的決賽中一較高下。
儘管球隊當家中鋒奧尼爾因拇指受傷缺席了賽季的前22場比賽，但是在哈達威的帶領下魔術仍然取得了17勝5負的不俗戰績。哈達威本人也被選為聯盟十一月的月最佳球員。隨後，奧尼爾復出，並以出色的表現彌補了自己因傷缺陣對球隊造成的影響。他帶領球隊連續第三次取得50場以上的勝利，並以一個四連勝結束常規賽季，將球隊的勝場數提高到了60場，創下隊史紀錄。
奧尼爾最終以26.6的場均得分(聯盟第三)、57.3%的命中率(第三)和2.13次封蓋(第九)結束了常規賽季。哈達威的得分(21.7)與助攻(7.1)也同時排在聯盟第十一位，此外他每場還能貢獻2.02次搶斷(聯盟第六)。球隊的神射手斯科特也完成了其職業生涯中最好的一個賽季：他的上場時間、得分、籃板、助攻均刷新了個人紀錄，並且以單賽季267個三分命中在聯盟記錄里留下了自己的名字。
季後賽開始後，正如人們預料的那樣，奧蘭多連續淘汰了底特律活塞與亞特蘭大老鷹闖入東部分區決賽，而他們的對手正是當年風頭最盛的芝加哥公牛隊。儘管魔術最終以0比4的總比分被擁有從棒球場回歸的籃球傳奇喬丹的公牛隊淘汰，但是0比4並不能反映出比賽的全部內容——年輕的魔術其實有機會拿下其中的兩場——而且就比賽內容而言，兩隊的第二次季後賽碰面也因為喬丹，奧尼爾，皮蓬(Scottie Pippen)，哈達威，羅德曼這些球星的出色發揮(格蘭特因傷只出戰了首場比賽)而足以寫入經典。四場比賽結束後，公牛以平均每場淨勝16.7分的成績挺進總決賽。而對於魔術隊來說，這意味著他們第三次季後賽之旅的完結。
更加不幸的是，魔術隊在下賽季里將失去他們的基石——當家中鋒沙奎爾-奧尼爾。這位讓球隊由魚腩之旅變成冠軍爭奪者的超級中鋒在賽季結束後以自由球員的身份加盟了洛杉磯湖人隊。
1996-2004：被傷病中斷的兩個1號傳奇
1996-97：受傷的心
儘管失去了沙奎爾-奧尼爾，賽季中又飽受球員傷病以及中途換帥的困擾。魔術仍然打入了季後賽，並僅以一場之差被邁阿密熱隊在首輪淘汰出局。
在季後賽首輪5局3勝的比賽里，邁阿密以在頭兩場比賽里一共淨勝魔術52分，並且在第三場的首節就取得了20分的領先優勢——即使是魔術最狂熱的支持者此時恐怕也已經放棄了希望。但是就在球隊被推到懸崖邊上的時候，哈達威——目前這支球隊當然的領袖，開始展現出他超強的個人能力：在第三場和第四場比賽里，哈達威分別拿下了42分和41分。球隊魔術般的再次回到邁阿密，與熱隊進行第五場的生死戰。而哈達威也成為第一位在季後賽裡面對帕特-萊利(Pat Riley)執教的球隊連續拿下40分以上的球員。在第五場比賽里哈達威依舊錶現出色，一人攻下33分，但這並不足以擊敗強大的熱隊。最終魔術還是以83比91敗下陣來。
達雷爾-阿姆斯特朗(Darrell Armstrong)，這名在常規賽季里並不顯山露水的球員在季後賽里卻成為球隊反攻的催化劑。身高僅為5尺11的阿姆斯特朗幾乎就是球隊整個賽季的縮影——剛毅、果敢、充滿鬥爭精神。他在一號位的出色發揮解放了哈達威，使得後者可以更加自由的在控球與組織間切換角色並將更多的精力投入到個人攻擊上，而實際效果也是立竿見影。
常規賽季開始前，魔術引進了經驗豐富的老將羅尼-塞卡利(Rony Seikaly)，而這一舉措也的確在一定程度上彌補了奧尼爾離隊造成的內線空虛。塞卡利平均每場貢獻17.3分以及9.5個籃板，並且在賽季初哈達威因膝傷休戰的日子裡擔當起了球隊的第一得分點。而哈達威並不是唯一的傷兵，事實上魔術的先發陣容在80場常規賽里一直飽受傷病困擾
魔術在全明星賽後的五連敗使球隊的勝率跌至五成以下(24勝25負)，這也直接導致了主教練布萊恩-希爾的下課。
取其位代之的是助理教練里奇-阿杜巴托(Richie Adubato)。他帶領球隊在剩下的比賽中打出了21勝12負的成績，從而確保了季後賽的資格。哈達威平均每場拿下20.5分，4.5個籃板和5.6次助攻。格蘭特每場也能貢獻12.6分和9個籃板。但是他因為手腕的傷勢無緣整個季後賽(這也是魔術對陣熱隊時的另一個不利因素)。但是憑心而論，在哈達威和阿姆斯特朗的帶領下，魔術隊在季後賽里所作的一切已經大大超出了人們的預測。
1997-98：戴利與J博士能讓魔術重現輝煌嗎？
在經歷了一個並不能讓人滿意的賽季之後，97年6月，魔術管理層為了重整河山聘請了兩位名人堂成員作為球隊的掌舵者：帶領活塞隊兩奪總冠軍的查克-戴利(Chuck Daly)出任球隊主教練，“J博士”朱利葉斯-歐文(Julius Erving)則出任球隊的執行副出席。這一切似暗示著魔術又將重新加入冠軍爭奪者的行列。但是恐怖的傷病再一次粉碎了球迷們的希望，球隊最終以恰好五成的勝率遺憾地被擋在季後賽的大門之外。
很不幸的是，戴利和歐文都沒有料到傷病對球隊的打擊能夠如此之大——一個賽季下來竟共有275人次因傷病缺席比賽。而其中最嚴重的莫過於球隊核心哈達威的左腿傷勢。這位連續四年的全明星後衛整整錯過了63場比賽。
因為哈達威的缺陣，尼克-安德森不得不肩負起球隊領袖的重任，而安德森也並沒讓隊友們失望。作為唯一一位從1989年建隊起就為魔術效力的球員，安德森在哈達威不在的日子裡每場拿下全隊最高的15.3分——雖然在12月和1月也因為傷病缺席了15場比賽，但是他下半賽季的出色表現彌補了這些。
在這個鬱悶的賽季里另一個利好的訊息是前鋒波-奧特洛(Charles “Bo” Outlaw)出色的表現。這名自由轉會而來的球員為球隊作出的貢獻大大超出人們的預期。他的命中率(55.4%)、封蓋(2.2)和搶斷(1.3)都位居全隊首位，並且他出色的速度和運動能力正好也與球隊籃板王格蘭特(8.1)搭配得相得益彰。
奧蘭多的另一位內線主將，中鋒羅尼-塞卡利在2月19日被交換至新澤西籃網隊，與他一起被打包的還有布萊恩-埃文斯(Brian Evans)，而魔術則得到老將大衛-本諾瓦(David Benoit)、因卡-戴雷(Yinka Dare)、凱文-愛德華茲(Kevin Edwards )以及一個第一輪選秀權。
3月20日，在魔術以100比75戰勝火箭以後，戴利獲得了他在NBA執教的第600場勝利，這使他成為第15位贏得600場勝利的教練，與此同時， 他達到這一成績所用的總場次也僅多於帕特-萊利，紅衣主教奧爾巴赫(Red Auerbach)，傑里-斯隆(Jerry Sloan)和唐-尼爾森(Don Nelson)，位列第5。
1998-99：過早完結的出色賽季
98-99賽季由於受到勞資談判的影響，常規賽季只進行了50場比賽。而就在這50場的縮水賽季里，戴利帶領著他的隊員們取得了33勝17負的東區最好戰績(與邁阿密熱、印第安那步行者並列)。而且魔術的主場比賽更是有著21勝4負的傲人戰績。
但是，季侯賽第一輪，躊躇滿志的魔術被阿倫-艾弗森(Allen Iverson)帶領的費城76人爆冷淘汰，早早退出了冠軍的爭奪。
魔術的達雷爾-阿姆斯特朗成為NBA史上第一位同時贏得最佳第六人和進步最快獎的球員。這名控球後衛每場貢獻13.8分以及聯盟第八的搶斷(2.16)，第十二的助攻(6.7)，並且還有著高踞聯盟第三的罰球命中率(90.4%)。
便士哈達威仍然是球隊的頭號得分手，場均得到15.8分以及聯盟第六的2.22次搶斷。尼克-安德森作為球隊的二號得分手每場也有14.9分入賬，並且在2月得到了自己職業生涯的第10,000分。另外，在4月30號與新澤西的比賽里安德森也有單場40分的佳績。
新賽季里又有兩名首輪新秀成為隊里的新面孔：前鋒馬特-哈普林(Matt Harpring )在賽季結束後以場均8.2分的成績入選NBA新秀第一隊，而中鋒麥可-多利亞克(Michael Doleac)也被選入新秀第二隊。
本賽季在奧蘭多也上演了“親人團聚”的一幕：多米尼克-威爾金斯(Dominique Wilkins)與 傑拉德-威爾金斯(Gerald Wilkins)在其職業生涯里首次為同一支球隊效力(威爾金斯兄弟職業生涯總計得到38,404分)。
儘管常規賽季結束時三支球隊戰績相同，邁阿密在戰績相同的情況下憑藉相互關係占優奪取了大西洋賽區以及東部分區第一的位置，而印第安那是中部賽區的第一因此必然排在東部賽區第二的位置上。魔術則不幸地被擠至東部第三，不得不與排名第六的費城76人為了分區半決賽的資格決一死戰。
76人與魔術在奧蘭多戰成1比1平，回到主場的他們在球迷狂熱的支持下再下一城(艾弗森一人就轟下33分外加10個搶斷)，將魔術逼上了懸崖。而魔術也沒能重現兩年前的奇蹟——第四場比賽艾弗森又用系列賽里最高的37分以及9次助攻將魔術擋在東部四強的門外。
1999-2000：家中的博士
開賽前和賽季中的人員變動使得魔術隊變成一支不再受到關注的球隊，幾乎沒有人再對這支隊伍抱有希望：全隊有十一人NBA球齡不超過三年，五人是非選秀球員，而這五人中竟有四人還是先發球員(約翰-阿米奇(John Amaechi)，達雷爾-阿姆斯特朗，波-奧特洛和本-華萊士(Ben Wallace))。
但是，這支不被人重視的球隊有著屬於他們自己的取勝武器：那就是積極的比賽態度與永不服輸的心。在這個賽季結束的時候，常規賽開始前一度被媒體大眾預測將在聯盟墊底的魔術出人意料地拿下了41勝41負的戰績——僅以一場之差被擋在季後賽門外。
自1999年6月14日到2000年2月24日，球隊總經理約翰-加布里埃爾(John Gabriel)一共做了37筆球員交易，涉及球員達到38人。通過這些交易，魔術不但騰出了寶貴的薪金空間，還在未來5年內囤積了9個首輪選秀權。而約翰-加布里埃爾也以出色的工作成績被選為1999-2000年度最佳球隊經理。當然，加布里埃爾最大的功績莫過於他大膽地簽下了毫無NBA執教經驗的道格-里弗斯(Glenn “Doc” Rivers)作為球隊的主教練。
菜鳥教練里弗斯整合球隊的能力給人們留下了很深的印象。在他的帶領下，每一位身著魔術球衣的球員都能為球隊勝利做出自己最大的貢獻——奧蘭多的板凳球員得分占全隊得分的48.2%，位居聯盟之首。這樣一群默默無聞的球員憑藉著完美的團隊協作和永不言敗的拼搏精神在不被任何人看好的情況下完成了球隊四年來最長的七連勝。
里弗斯出色的執教成績也得到了聯盟的承認——聯盟第一次將賽季最佳教練的獎項頒發給一位沒有帶隊打入季後賽的教練。而這也是該獎項第三次頒發給執教勝率小於或等於50%的教練，第五次頒發給初次執教的菜鳥教練。
阿姆斯特朗作為隊長是球隊當之無愧的核心。他的得分(16.2)、助攻(6.1)、搶斷(2.06)和出場時間(31.6)均為全隊最高。同時他也是“積極的比賽態度與永不服輸的心”的完美體現。阿姆斯特朗的罰球命中率(91.1%)排名聯盟第三，搶斷排名第六，助攻也排在第十六位，並且是全聯盟打滿全部82場比賽的26人中的一位。
2000-01：新星的誕生
2000年的夏天，擁有大量薪金空間的魔術隊在自由人市場裡大展拳腳，他們一口氣簽下了兩位當時最炙手可熱的自由球員：格蘭特-希爾(Grant Hill)和特雷西-麥克格雷迪。與此同時，出色的人員運作也使球隊在引入強援的同時仍然保留了上賽季取得成功的基本陣容。
賽季開始前，人們對這支全新的魔術報以很高的期望。但是天有不測風雲，常規賽季只進行了四場比賽格蘭特 希爾就因傷不得不缺席賽季餘下的所有比賽，這對擁有八名新面孔，平均年齡倒數第八的魔術隊無疑是一個沉重的打擊。然而，在道格-里弗斯的率領下頑強的魔術仍然以43勝39負的成績闖入季後賽。這也是魔術隊在八年里第六次闖入季後賽，以及連續九年勝率保持在五成以上。
從1月30日到2月18日，魔術一直享受在球隊史上最長的九連勝之中。以這九連勝為契機，球隊在後半賽季里取得了24勝17負的好成績，最終以東部第七的身份進入季後賽挑戰米爾沃基雄鹿隊。然而由於實力上的差距，魔術在季候賽的賽場上只獲得了四次出場機會，雄鹿以3比1的總比分淘汰魔術進入下一輪。
希爾的缺陣給了特雷西-麥克格雷迪 更多表現的機會。這位四年NBA球齡的鋒衛搖擺人本賽季全面爆發，在每場40分鐘的出場時間裡能夠貢獻26.8分、7.5 個籃板、4.6 次助攻、1.53次封蓋以及1.51次搶斷。作為全隊的得分王，麥克格雷迪的籃板、助攻、封蓋以及搶斷也都排在全隊第二位。同時他也是繼阿姆斯特朗之後又一位獲得進步最快球員獎的魔術隊球員。憑藉本賽季出色的表現，麥克格雷迪成功入選東部全明星隊以及NBA第二最佳陣容。
除了麥克格雷迪的爆發，魔術隊也從選秀中得到了豐厚的回報。邁克-米勒(Mike Miller)，這名鋒衛搖擺人隨著賽季的進行一直穩定地進步。賽季結束時他的場均技術統計為14.0分，4.4個籃板， 1.9 次助攻和33.4分鐘的出場時間。作為聯盟唯一一位82場全勤的新人，他還打破了球隊的新秀三分出手以及命中紀錄(出手364次，命中148次)。
邁克-米勒的出色表現使他最終當選為賽季最佳新人並順理成章地入選新秀第一隊。
2001-02：麥迪傳奇仍在繼續
在主教練道格-里弗斯的帶領下，魔術隊在九個賽季里第七次也是連續第二次闖入季後賽。他們44勝38負的成績也讓球隊勝率連續十年不低於五成。而魔術追逐總冠軍的夢想又一次在季後賽第一輪被夏洛特黃蜂粉碎。
2002-03賽季的麥克格雷迪已經成長為一位真正意義上的超級巨星，他的得分(25.6分，聯盟第四)、籃板(7.8)、出場時間(38.3)均為全隊之首。5.3次助攻，1.57次搶斷也僅在阿姆斯特朗之後位列第二。最終“T-Mac”成功進入NBA最佳陣容第一隊，並且在最有價值球員(MVP)的評比中也得到了第四的積分。連續第二年入選全明星的麥克格雷迪也是聯盟中僅有的兩位得分超過25分，籃板、助攻均超過5個的球員之一。
職業生涯平均每場能有21.4分，7.9 個籃板，6.2次助攻入賬的六次全明星球員格蘭特-希爾本賽季仍然深受傷病困擾——他因為左踝的傷勢缺席了68場比賽。而魔術隊的其他球員也沒有逃出傷病的魔爪——整個賽季下來共有211人次缺席比賽——用人上的捉襟見肘迫使里弗斯先後使用過18套不同的先發陣容。
儘管霉運連連，魔術隊仍然保持了強大的攻擊火力。他們的場均得分排名聯盟第四(100.5)，三分球得分也排名聯盟第八。27勝14負的主場戰績在東部也僅次實力強大的新澤西網隊。
作為球隊隊長之一的達雷爾-阿姆斯特朗仍然是魔術拼搏精神的代表。他是球隊的助攻王(5.5次，聯盟第十九)和搶斷王(1.91次，聯盟第六)，並且依舊保持著極高的罰球命中率(88.8%，聯盟第三)。
賽季結束後，魔術的陣容里又補充了幾個新面孔：控球後衛傑奎-沃恩(Jacque Vaughn)，強力前鋒肖恩-坎普(Shawn Kemp)和新人里安-亨弗里(Ryan Humphrey)。他們的加盟給魔術帶來了球隊所急需的板凳深度。
2002-03：季後賽，苦澀的失敗
2002-2003賽季是魔術隊連續第十一次以過半的勝率結束常規賽。42勝40負的成績雖然足以將球隊連續第三年送入季後賽，但是這也意味著他們將與東部戰績最好的活塞隊在首輪碰面。讓人大跌眼鏡的是，賽前不被人們看好的魔術隊不但從活塞的主場搶回一場勝利，更在自己的主場連下兩城，把奪冠熱門活塞隊逼入之差一場就要遭到淘汰的絕境。3比1的總比分似乎已經預示著又一個黑八奇蹟將要誕生。但是老天在這時和所有奧蘭多人開了一個玩笑，場場都是背水一戰的活塞隊奇蹟般地連贏三場，最終以4比3的比分將一支腳已經踏入下一輪的魔術隊無情地拽了回來。
季後賽令人扼腕嘆息的失利並不能否定魔術隊的整個賽季。特雷西-麥克格雷迪經過六年職業聯賽的磨礪，終於成為聯盟屈指可數的幾位巨星之一。聯盟得分王(場均32.1分)，6.5個籃板，5.5次助攻，這樣出色全面的表現讓麥迪毫無爭議地入選NBA最佳陣容第一隊，並且在MVP的評選中也位列第四。
而麥克格雷迪也並不是球隊唯一的閃光點，二月份從孟菲斯交易來的新人戈丹-吉里切克(Gordan Giricek)和德魯-古登(Drew Gooden)也讓人眼前一亮。德魯-古登最終以12.5分，6.5 個籃板的成績被入選最佳新秀第一隊，而戈丹-吉里切克的名字也同時出現在新秀二隊的名單里。除了這兩名表現出色的新秀，帕特-加里蒂(Pat Garrity )也被選入全明星周末的三分遠投大賽(共有6名球員參加，人選分別是從上一年三分球大賽的冠軍、三分球得分最多的球員以及三分球命中率最高的球員中產生，最終加里蒂在本屆比賽中獲得了第四名)
格蘭特-希爾在本賽季仍然飽受傷病困擾，他只出戰了29場比賽就因左踝舊傷復發不得不再次進行手術。而手術也意味著這位傷病累累的超級巨星的又一個賽季提前結束。
雖然只是畫餅充飢，但是人們總是忍不住去猜想季後賽與活塞隊的七場大戰里如果魔術擁有一個健康的希爾，那最終又將會是什麼結果……
2003-04：困難的一年
本來魔術應該有足夠的理由來樂觀面對建隊的第15周年——在與活塞進行了驚心動魄的七場大戰後，輿論一致認定下賽季的魔術會是一支不可小覷的隊伍。而強力前鋒朱萬-霍華德(Juwan Howard)和控球後衛泰倫-盧(Tyronn Lue)的加入更使得原本就擁有超級球星麥克格雷迪的魔術如虎添翼。
然而，不幸的事情接踵而來，在贏得對紐約的開門紅後，球隊不可思議地連續19場沒有取得勝利。在創紀錄的連敗嚴重打擊了球隊士氣的同時，傷病問題也像夢魘一樣揮之不去：希爾繼續缺陣整個賽季，帕特-加里蒂在僅有的一次出場比賽後也步了希爾的後塵。
當這個令人鬱悶不已的賽季結束時，21勝61負的戰績無疑讓球迷十分失望。但是，魔術隊也並不是一無是處。麥克格雷迪連續第二年成為聯盟得分王(28.0)，並且在2月2日的比賽里拿到職業生涯的第10000分。這也使他成為拿到10000分的年齡第二小的球員。而3月10號與華盛頓奇才的比賽無疑是麥克格雷迪超強得分能力的最好詮釋——手感奇佳的麥迪單場轟下了創隊史紀錄的62分。
球隊差勁的表現直接影響到了領導班子的調整。十一月，約翰尼-戴維斯(Johnny Davis)被提升為主教練。三月，約翰-維斯布羅德(John Weisbrod)被任命為球隊新的總經理。年輕的魔術希望憑藉新的大腦重塑球隊昔日的輝煌——加入NBA十五年的魔術隊並不習慣沉淪，也絕不甘於沉淪。
2004-2009：超人來到奧蘭多
2004-05：新時代
奧蘭多魔術在2004-05賽季開始的時候迎來了一個新的籃球時代，球隊的隊服做了更換，而繁忙的休賽期也讓陣容煥然一新。這個賽季清晰地顯示出球隊力求避免另一個如同他們在2003-04賽季體驗的21勝61負悲慘戰績的決心。
魔術的賽季開始於他們隊史的第三個狀元簽，來自喬治亞州亞特蘭大的奈史密斯獎得主德懷特-霍華德，同時通過選秀日交易從丹佛掘金得到了聖約瑟夫大學球員賈米爾-尼爾森的選秀權，讓他們的這次選秀很可能成為隊史最好的一次選秀。
球隊陣容在2004年1月29日進行了更大的調整，球隊送走了全明星球員、聯盟得分王特雷西-麥克格雷迪及其他球員，從休斯頓換來了史蒂夫-弗朗西斯、卡蒂諾-莫布里和凱爾文-卡托。
霍華德讓奧蘭多重新燃起希望奧蘭多感覺到了他們良好的選秀和自由球員及交易的引援帶來的影響，這些引援還包括希度-特克格魯和托尼-巴蒂。球隊在前20場比賽取得了13勝7負的良好開局，隨後他們繼續在弗朗西斯和籃板機器霍華德的帶領下在全明星周末前拿到了28勝24負的成績。
但是下半賽季球隊有了變化。莫布里很快被交易到薩克拉門托，換來了道格-克里斯蒂，然後，在一個月中只贏得三場比賽之後，球隊在2005年3月17日任命克里斯-簡特為代理主教練。特克格魯、帕特-加里蒂和格蘭特-希爾的傷病傷害了球隊的最後18場比賽，奧蘭多以36勝46負結束了這一年。
儘管賽季以失望告終，魔術仍有許多亮點安慰艱難的賽季。希爾書寫了聯盟年度最令人欣慰的故事，他從前後5次手術中恢復，在本賽季場均貢獻19.7分，並贏得了聯盟的體育道德風尚獎，以及東部全明星首發的位置。
用狀元簽選擇霍華德也被證明是聰明的決定，他在新秀賽季成為聯盟僅有的8位場均兩雙的球員之一(場均12.0分10.0籃板)，同時入選了NBA最佳新秀陣容第一隊。尼爾森在下半賽季進步明顯，入選了最佳新秀第二隊。在年輕核心和健康希爾帶領下，魔術對下賽季抱有了更高期待。
2005-06：季中大交易
在魔術在傑克遜維爾重新集中，在被佛羅里達大學開始季前訓練營的時候，球隊又迎來了一些新面孔，包括教練組。布萊恩-希爾，魔術歷史上獲勝最多的主教練回歸球隊開始了他在奧蘭多的第二次任期，準備率領球隊重返季後賽。
夏天加盟球隊的還有肯揚-杜林，他在邁阿密短暫停留後來到奧蘭多，球隊期待他和第二輪新秀特拉維斯-迪納爾一起補強球隊的後場。此外，波-奧特洛自2001-02賽季離開後首次重返奧蘭多。不過奧蘭多沒能得到他們的首輪新秀弗蘭-瓦斯奎斯，後者選擇留在歐洲打球，而非立刻加入NBA。
雖然球隊順利開始了訓練營和季前賽，魔術在卻在常規賽來臨前被一些壞訊息所打擊。首發前鋒格蘭特-希爾被查出運動性疝氣，需要接受手術和3-6周的恢復期。
在希爾因傷缺陣的情況下，球隊開季的先發陣容包括德懷特-霍華德、希度-特克格魯、托尼-巴蒂、德肖恩-史蒂文森和史蒂夫-弗朗西斯。
球隊在前兩個月總共取得12勝15負，期間最閃耀的表現是德懷特-霍華德在對山貓的比賽中以21分20個籃板烤焦對手，成為NBA歷史上最年輕的單場拿到雙20的球員。
一月初球隊遇到了殘酷賽程，球隊在2006年最開始的8場比賽中輸掉7場，禍不單行的是賈米爾-尼爾森因為右腳扭傷將缺席此後的20場比賽。在全明星周末前只有19勝32負的情況下，魔術決定為未來而重建，將凱爾文-卡托和一個受限制首輪選秀權送到底特律活塞，換來了卡洛斯-阿羅約和達科-米利西奇。一周之後，魔術將弗朗西斯送到紐約尼克斯，換來了特雷沃-阿里扎和前魔術球星安芬尼-“便士”-哈達威的到期契約。
在戰績滑落到20勝40負之後，球隊開始和新來者們團結起來，以同期聯盟最佳的16勝6負結束了球隊的最後22場比賽，以微弱的差距錯失了東部第八名和季後賽資格。
2006-07：超人的首次季後賽之旅
魔術依靠上賽季的強勢收尾為新賽季開了個好頭，他們早早打出13勝4負，排名分區第一。不過，到了12月傷病開始侵襲魔術，他們在隨後的14場比賽中僅勝4場。魔術在新年到來之後有所恢復，連勝5場，不過這只是一次小小的反彈，1月底他們重新開始滑落。儘管德懷特-霍華德持續向著明星水準進步，並首次入選了全明星，魔術的下滑仍在繼續，跌破了50%勝率大關。魔術又一次面臨錯過季後賽的危險，他們終於找回了11月時候的比賽狀態。最終，靠著賽季最後4場比賽取得的4連勝，球隊以40勝42負的成績四年來第一次殺入季後賽。
不走運的是，他們在季後賽的對手過於強大，老練的底特律活塞讓他們無法在季後賽再進一步，魔術連丟四場被橫掃出局。賽季結束後，魔術對主帥作出調整，解僱了布萊恩-希爾。球隊希望有一個重量級且備受佛羅里達球迷愛戴的人選接替希爾，於是他們聘請了率領佛羅里達短吻鱷隊連續兩年拿到NCAA冠軍的比利-多諾萬。但是多諾萬在簽約幾天后改變了想法，請求解除雙方的契約，以便他繼續留在短吻鱷隊執教。在魔術隊和多諾萬達成協定之後，魔術隊聘請了前邁阿密熱火的主教練斯坦-范甘迪。不過這還不是球隊夏季最大的動作，他們隨後從西雅圖超音速簽下了被熱追的自由球員拉沙德-劉易斯。
2007-08：真正進入強隊行列
拉沙德-劉易斯的到來以及德懷特-霍華德的持續成熟成為魔術在新帥斯坦-范甘迪帶領下取得良好開局的關鍵因素，他們在前20場比賽贏得16場。不過隨後的一個半月魔術表現不佳，只有8勝13負的表現。雖然如此，魔術依然保持著東南區的第一名，其他球隊基本都不構成威脅。到了全明星周末上，德懷特-霍華德占據了舞台中心，他在紐奧良贏得了扣籃大賽冠軍。隨著賽季不斷進行，魔術開始在三月份重新打出好球，以最後六周內15勝7負的強勢發揮作為賽季的註腳，以52勝30負的成績贏得了1996年以來的第一個分區冠軍。這個分區冠軍的功勞很大一部分歸於希度-特克格魯，他場均貢獻生涯新高的19.5分，贏得了聯盟最快進步獎。
季後賽第一輪，魔術面對的是多倫多猛龍，依靠德懷特的25分22籃板球隊得以114-100取勝首場。第二場球隊依然需要霍華德打出29分20籃板的優異表現，才以104-103的分數苦戰過關，贏得系列賽2-0的優勢。在輸掉第三場扭個之後，魔術依靠拉沙德-劉易斯和希度-特克格魯的三分投射106-94擊敗猛龍，贏得了系列賽3-1的絕對優勢。隨後在第五場魔術102-92再次取勝並淘汰了猛龍，12年來第一次贏得季後賽系列賽，而霍華德也在這一場拿下他系列賽的第三個雙20表演。不過第二輪他們撞到了一堵高牆，底特律活塞隊。儘管德懷特-霍華德打出優秀表現，魔術在底特律的前兩場都以失利告終。拉沙德-劉易斯在第三場得到33分，魔術111-86輕取對手保留了一線生機，不過魔術在第四場遭遇壓垮他們的89-90惜敗，活塞隨後91-86取勝第五場，進入東部決賽。
2008-09：隊史第二次總決賽
期待著更進一步的魔術隊很快控制了東南賽區的句式，他們在賽季第一個月打出13勝4負，德懷特-霍華德繼續表現出聯盟頂級中鋒的實力。年僅23歲的霍華德成為了全明星以及內線的統治力量，不斷拿到兩雙，在聯盟籃板和封蓋榜上都名列前茅，並成為NBA歷史上最年輕的年度最佳防守球員。霍華德的強悍防守幫助魔術整個賽季都控制著東南賽區，並以59勝23負拿到了分區頭名。
季後賽中，魔術遭遇艱苦開局，他們首場比賽98-100令人震驚地輸給費城76人和安德烈-伊戈達拉的壓哨跳投，其中第四節76人單節打了魔術一個35-19。在主場贏下第二場之後，魔術在第三場再次遭遇意外，賽迪斯-楊終場前兩秒鐘的上籃讓76人96-94取勝，重新取得系列賽領先。不過第四場霍華德接管了籃下，以18分18籃板的表現幫助魔術隊以84-81追平大比分，隨後他在第五場打出雙24的表現，魔術91-78取得3-2的領先。魔術最終在第六場114-98獲勝結束了系列賽，儘管這一場德懷特-霍華德因為此前第五場中肘擊對手的薩穆埃爾-戴勒姆波特而被禁賽，未能上場。第二輪魔術遇上了衛冕冠軍波士頓凱爾特人，他們開局順利，客場95-90拿下首戰，德懷特-霍華德化身籃板怪獸取下22個籃板。不過，衛冕冠軍開始反擊，在隨後的4場比賽贏下3場，拿到了系列賽3-2的領先，將魔術逼到了再次在第二輪被淘汰的邊緣。不過，在德懷特-霍華德再次打出23分22籃板強勢表現的情況下，魔術主場83-75取勝將系列賽逼入第七場。第七場的英雄是希度-特克格魯，他以25分12助攻接管比賽，霍華德抓到16個籃板，魔術在對手的主場以101-82推翻了凱爾特人。
在東部決賽面對克利夫蘭騎士，魔術令人震驚地奪取了首場比賽的勝利，他們在霍華德30分13籃板的帶領下逆轉了半場15分的落後，107-106讓克利夫蘭人嘗到了賽季第三場的主場失利。魔術只差幾秒鐘就能在克利夫蘭取得兩連勝，但是勒布朗投中壓哨球，為騎士扳平了總比分。不過，系列賽回到奧蘭多後魔術繼續讓騎士遭遇挫折，擁有常規賽最佳戰績的騎士隊被魔術用外圍火力的優勢連贏兩場而毫無應對辦法。在騎士贏下第五場之後，魔術最終依靠霍華德生涯新高的40分在第六場103-90贏下第六戰，完成了這個大冷門，隊史第二次殺入總決賽。
總決賽中魔術再次扮演弱勢一方，面對洛杉磯湖人。不過這一次他們沒能在開局占優，首場就遭受75-100的敗局。魔術在第二場將比賽逼入加時，不過在湖人101-96取勝之後只得帶著0-2的比分回主場。魔術在第三場108-104拿到了球隊再總決賽的首場勝利，帶著追平系列賽的希望，魔術在第四場將領先保持到了比賽後半段。不過德里克-費舍爾終場前4.6秒的三分球將比賽拖入加時，湖人隨後99-91拿下比賽，3-1。湖人隨後在第五場99-86再次取勝，在奧蘭多拿到了總冠軍獎盃。賽季結束後，魔術的希度-特克格魯作為自由球員離開球隊，不過他們很快填補了這一空缺，從新澤西籃網得到了文斯-卡特、里安-安德森，籌碼是拉夫-阿爾斯通、托尼-巴蒂和考特尼-李。
2009-10：收穫與失望
本賽季常規賽魔術以59勝23負的最終戰績追平上賽季，位居東部第2 。魔術在賽季前便是總冠軍的大熱門之一，由於重大的人員更替，特別是球隊核心特科格魯的離開，新交易來的卡特不能很快的融進球隊體系，導致球隊在一段時間內沒有找到很好的比賽節奏，賽季前2個月隊里不斷在磨合 卡特並沒有轉變原來的打球習慣，有球在手才能進攻的特色依舊，而霍華德和幾個其他主力則出手減少。1月卡特突然遭遇低谷，球隊接連輸給多支弱旅。但是1月的陣痛讓魔術隊和卡特找到了感覺和打法，球隊終於突出了霍華德的主導位置，卡特也改變打法更無私和高效。2月以來球隊不斷好轉拿下多場硬仗，迎來數次連勝，說明魔術的磨合基本成功。
魔術在季後賽首輪遭遇季後賽新軍山貓隊。山貓雖然沒有強力內線與魔術抗衡，但是全隊在老帥拉里-布朗的調教下形成了一套行之有效的防守方針，並在實際比賽中對魔術造成了不小的困擾，雖然大比分魔術4：0橫掃山貓，但其中有三場山貓輸在最後時刻。到了次輪對陣老鷹時情況又大不相同，在常規賽砍下53勝的老鷹面對擁有霍華德以及外線兇猛火力的魔術幾無還手之力，場均輸分接近28分被橫掃。在東部決賽里魔術對上凱爾特人，後者依靠其兇悍的防守和快節奏的攻防在一定程度上限制了霍華德的發揮，從而掐住了魔術的命脈，最終魔術以2：4的總比分被淘汰出局。
