路易斯安那州身高7尺1,体重301磅的天才中锋沙奎尔?奥尼尔。自从奥尼尔加入魔术队后,球队开始向着好的方向发展。丹尼斯?斯科特、特里?卡特莱奇、斯科特?斯凯尔斯、尼克?安德森与代替格雷格?凯特出任首发中锋的沙奎尔?奥尼尔组成了球队新的首发阵容。到1992-93赛季结束时,魔术队的战绩比起1991-92赛季时提升了整整二十场,成为当赛季联盟进步最快球队。最终魔术队用一场对老鹰队的胜利结束了这个最成功的赛季(位列大西洋赛区第四位),却遗憾地被印第安那挤出了季后赛。球队糟糕的客场成绩是无缘季后赛的主要因素,14胜27负的客场战绩与27胜14负的主场战绩形成截然反差。在球员方面:球队得分王奥尼尔场均砍下23.4分,总分1893分以及56.2%的命中率都是球队的新纪录(场均13.9个篮板与3.53次封盖),是联盟中唯一一位在得分(第8),篮板(第2),封盖(第2)和命中率(第4)都排入前十的球员。尼克?安德森成为奥尼尔的好帮手,场均得到19.9分并且几乎所有的技术统计都为职业生涯新高。丹尼斯?斯科特和斯科特?斯凯尔斯也有场均15+的得分。斯凯尔斯仍然是高效的组织者,一个赛季下来送出职业生涯最高的735次助攻(场均9.4次,联盟第三)。在1993年选秀大会上,奥兰多魔术队利用手上的第一选秀权完成了最大的一笔选秀当日交易:当时密歇根大学的克里斯?韦伯是当时公认的状元不二人选,然而已经拥有奥尼尔的魔术队却对来自孟菲斯的后卫“便士”安芬尼?哈达威更感兴趣。因此魔术选中韦伯后马上与选中哈达威的勇士队进行了交易。1993-94赛季,魔术队意料之中地爆发,球队不但以50胜的成绩闯入季后赛,沙奎尔?奥尼尔和安芬尼?哈达威的存在更是使魔术成为职业运动领域中最有吸引力的球队之一。魔术队在全明星赛前27胜20负,全明星周末结束后23胜12负,最终以大西洋分区第二的身份挺进季后赛,但是在首轮便倒在了当年的季后赛黑马步行者脚下,后者则一直杀入了东区决赛。1994-95赛季,奥兰多魔术球队便以57胜25负的战绩成为了东部的老大,并且在季后赛里一路击败波士顿凯尔特人、芝加哥公牛以及印第安纳步行者队昂首闯入总决赛。但首次踏上总决赛赛场的魔术队最终被经验丰富的卫冕冠军休斯敦火箭队以4-0的总比分击败。在这个赛季,沙奎尔?奥尼尔与安芬尼?哈达威组成了魔术队才华横溢、令人羡慕的双人核心。奥尼尔在他职业生涯的第三年终于拿下了nba常规赛季的得分王(29.3),另外还有排名联盟第三的篮板(11.4)、第二的命中率(58.3%)以及第六的封盖(2.43),最终入选nba第二最佳阵容。1995-96赛季,由沙奎尔?奥尼尔、霍勒斯?格兰特、尼克?安德森、丹尼斯?斯科特和安芬尼?哈达威组成先发五虎的魔术队用出色的战绩证明了1994-95赛季打入总决赛绝非侥幸。魔术队在常规赛里秋风扫落叶般的拿下60个胜场,蝉联大西洋分区冠军。在季后赛中,奥兰多魔术队连续淘汰底特律活塞队与亚特兰大老鹰队闯入东部分区决赛,而他们的对手正是当年风头最盛的芝加哥公牛队。魔术队最终以0比4的总比分被公牛队淘汰出局。在球员方面:奥尼尔因拇指受伤缺席了赛季的前22场比赛,但是在哈达威的带领下魔术仍然取得了17胜5负的不俗战绩。哈达威本人也被选为联盟十一月的月最佳球员。奥尼尔最终以26.6的场均得分(联盟第三)、57.3%的命中率(第三)和2.13次封盖(第九)结束了常规赛季。哈达威的得分(21.7)与助攻(7.1)也同时排在联盟第十一位,此外他每场还能贡献2.02次抢断(联盟第六)。1996-97赛季,魔术队失去球队的基石——中锋沙奎尔?奥尼尔。这位让球队由鱼腩之队成冠军争夺者的超级中锋在赛季结束后以自由球员的身份加盟了洛杉矶湖人队。尽管失去沙奎尔?奥尼尔,赛季中又饱受球员伤病以及中途换帅的困扰。魔术仍然打入了季后赛,并仅以一场之差被迈阿密热队在首轮淘汰出局。
在经历了一个并不能让人满意的赛季之后,1997年6月,魔术管理层为了重整河山聘请了两位名人堂成员作为球队的掌舵者:带领活塞队两夺总冠军的查克?戴利出任球队主教练,“j博士”朱利叶斯?欧文则出任球队的执行副出席。1997-98赛季,恐怖的伤病再一次粉碎球迷们的希望,球队最终以恰好五成的胜率遗憾地被挡在季后赛的大门之外。一个赛季下来竟共有275人次因伤病缺席比赛。而其中最严重的莫过于球队核心哈达威的左腿伤势,这位连续四年的全明星后卫整整错过了63场比赛。因为哈达威的缺阵,尼克?安德森不得不肩负起球队领袖的重任,作为唯一一位从1989年建队起就为魔术效力的球员,安德森在哈达威不在的日子里每场拿下全队最高的15.3分。1998-99赛季,由于受到劳资谈判的影响,常规赛季只进行50场比赛。而就在这50场的缩水赛季里,魔术队取得了33胜17负的东区最好战绩(与迈阿密热、印第安那步行者并列)。而且魔术的主场比赛更是有着21胜4负的傲人战绩。但是在季后赛第一轮,魔术队被阿伦?艾弗森带领的费城76人队爆冷淘汰,早早退出了冠军的争夺。但是球队中的达雷尔?阿姆斯特朗成为nba史上第一位同时赢得最佳第六人和进步最快奖的球员。这名控球后卫每场贡献13.8分以及联盟第八的抢断(2.16),第十二的助攻(6.7),并且还有着高踞联盟第三的罚球命中率(90.4%)。