但当年最风光的球队无疑是传奇球星乔丹的回归以及篮板王罗德曼加盟的芝加哥公牛，他们在八十二场常规赛中取得了不可思议的72胜10负的战绩——当常规赛季结束时，几乎一切迹象都表明这两支球队将在东部7战4胜的决赛中一较高下。
华山论剑前，奥兰多用底特律活塞与亚特兰大老鹰进行了祭剑，但那年碰到的乔丹已经成神成圣，0∶4，魔术又被剃了个光头。
1996年，奥尼尔新秀合约到期，面对奥尼尔提出的天价合同，魔术置之不理，最终鲨鱼西游，去了湖人。
失去了奥尼尔的哈达威孤单影只，虽然杀进季后赛但首轮面对热火队，哈达威在第三场和第四场的背靠背的季后赛连续拿下40分，系列赛场均超过30分，但最终魔术还是败下阵来。
1998—1999年因为劳资谈判，常规赛仅仅有50场，魔术取得了33胜17负的东区最好战绩（与迈阿密热火、印第安纳步行者并列）。
但这年季后赛球队还是在第一轮输给了艾弗森领军的费城76人队。
1999年6月14日到2000年2月24日，球队总经理一共做了37笔球员交易，涉及球员达38人，这也为球队腾出了薪金空间。
2000年奥兰多放出卫星要以顶薪网罗邓肯和格兰特·希尔，并以一个300万拿下麦迪。
联盟都为这个计划发出惊呼，但最终邓肯没有得到，球队得到了麦迪和希尔。
当年魔术以43胜39负的成绩闯入季后赛。
这也是魔术队在八年里第六次闯入季后赛，以及连续九年胜率保持在五成以上。
麦迪场均26.8分、7.5个篮板、4.6次助攻、1.53次封盖以及1.51次抢断。
但因为希尔的缺阵，在季后赛首轮面对雄鹿时1∶3败下阵来。
2001—2002赛季，麦迪传奇仍在继续，麦迪已经成长为一位真正意义上的超级巨星，他的得分（25.6分，联盟第四）、篮板（7.8个）、出场时间（38.3分钟）均为全队之首。
5.3次助攻，1.57次抢断也是球队第二。
希尔本赛季仍然深受伤病困扰——他因为左踝的伤势缺席了68场比赛。
而魔术队的其他球员也没有逃出伤病的魔爪——整个赛季下来共有211人次缺席比赛——用人上的捉襟见肘迫使主教练先后使用过18套不同的先发阵容。
2002—2003赛季是魔术队连续第十一次以过半的胜率结束常规赛。
42胜40负的成绩虽然足以将球队连续第三年送入季后赛，但是这也意味着他们将与东部战绩最好的活塞队在首轮碰面。
让人大跌眼镜的是，赛前不被人们看好的魔术队不但从活塞的主场抢回1场胜利，更在自己的主场连下两城，把夺冠热门活塞队逼入只差一场就要遭到淘汰的绝境。
3∶1的总比分似乎已经预示着又一个黑八奇迹将要诞生。
但是老天在这时和所有奥兰多人开了一个玩笑，场场都是背水一战的活塞队奇迹般地连赢三场，最终以4∶3的比分，将一只脚已经踏入下一轮的魔术队无情地拽了回来。
经过六年职业联赛的磨砺，麦迪终于成为联盟屈指可数的几位巨星之一。
麦迪这个赛季成为联盟得分王，场均32.1分6.5个篮板5.5次助攻，这样出色全面的表现让麦迪毫无争议地入选NBA最佳阵容第一队，并且在MVP的评选中也位列第四。
2003—2004年，魔术仍旧遭遇到伤病的困扰，麦迪蝉联了联盟得分王，场均拿下28分。
但球队仅仅取得21胜61负的战绩。
随后麦迪2005年去了休斯敦火箭，球队2004年选中的状元魔兽中锋霍华德在经过两年历练后也成长为联盟的明星，但魔术需要改进的还有很多！德怀特·霍华德球员篇变态版的联盟魔兽说德怀特·霍华德是变态版的魔兽，其实一点贬义都没有。
虽然霍华德在芝加哥曾和利文斯顿两人举行了男子成人仪式，但记者再次采访他的时候，霍华德还是认真地说：什么？你说那是嫖妓，我那是为了拯救她们堕落的灵魂。
作为一个男人，霍华德敢做敢当，作为一个球员，霍华德用他那嘴吻篮筐，爆扣联盟所有内线的霸气为自己赢得了一个变态魔兽的雅号。