奥兰多魔术队在1989——1990赛季加入NBA。他们仅用了很短的时间就成为冠军的有力争夺者。当魔术在1992年引进中锋大鲨鱼奥尼尔后，他们的竞争实力陡然增强，成为联盟中最受欢迎的队伍之一。

　　在奥兰多魔术加入NBA的四年前，当地的发展商银行家吉姆-休伊特便开始了将NBA登录奥兰多的想法并行动了起来。他首先将费城76人队的总经理帕特-威廉姆斯请到了佛罗里达。接着威廉姆斯开始推广奥兰多魔术的T恤衫，球帽和其他商品，并给当地预定球票的观众享受100美金的赛季套票优惠。

　　休伊特在提交了10万美金的“报名费”之后，奥兰多成为NBA扩军的候选人之一。一年之后的4月22日NBA董事会投票决定奥兰多在1989——1990加入NBA。

　　魔术队是NBA的新军之一，1989年才加入NBA。跟许多初入NBA的球队一样，魔术队经历了前几个失败的赛季。1989-1990赛季，魔术队以18胜64负收场。随后两个赛季也不如意，1991年31胜51负，1992年21胜61负。

　　魔术队的历史在第四个赛季发生了变化。1992年魔术队获得头号选秀权，他们选中了路易斯安那州立大学的沙克-奥尼尔（Shaquille O’Neal）。奥尼尔几乎是以一已之力，带动了魔术队。当赛季奥尼尔平均每场拿下23.4分和13.9个篮板3.53个盖帽，成为自1985年乔丹以后第一个进入全明星赛先发阵容的新秀。魔术队以41胜41负的成绩结束了1992－93赛季常规赛，他们仍然未能进入季后赛。

　　不过1993年未能进入季后赛，对魔术队来说几乎是一个好事，因为他们为此连续第二年得到了头号选秀权，魔术队挑中了“便士”哈达威（Anfernee Hardaway）。哈达威在第一个赛季每场就拿下了16.0分6.6次助攻5.4个篮板和2.32次抢断。得到哈达威的协助，奥尼尔也更加势不可挡，平均每场拿下了29.3分，与大卫-罗宾逊（David Robinson）争夺联盟“得分王”的称号。大卫-罗宾逊在最后一场比赛中拿下了71分，才以微弱的优势战胜奥尼尔，但奥尼尔59.5％的命中率在联盟中却无出其右者。当赛季魔术队取得了50胜32负，终于第一次闯入季后赛。但首轮就被步行者队淘汰出局。

　　1994年，奥尼尔入选“梦二队”并载誉归来，带着冠军回来的奥尼尔后气势更盛，魔术队在奥尼尔和哈达威的率领下，取得了东部最佳的57胜25负。在季后赛中，魔术队先后淘汰了凯尔特人队、公牛队和步行者队，与西部冠军火箭队在总决赛中相遇。总决赛中，年轻的奥尼尔未能抵挡住老练的奥拉朱旺（Hakeem Olajuwon），魔术队在第一场虽然将火箭队逼入了加时赛，但最后仍以118比120失利。此后火箭队势如破竹，最终以总比分4比0拿到了本队第二个总冠军。

　　虽然冲击冠军未果，奥尼尔却在NBA打出了名头。1995-1996赛季，他率魔术队取得了60胜22负的佳绩，再次进军季后赛，并且打入东区总决赛。不过此次奥尼尔面对的是复出的乔丹所率领的公牛队，公牛队在东部决赛中以4比0淘汰魔术队。

　　1996年奥尼尔离开奥兰多魔术队转投洛杉矶湖人队，魔术队神奇的“魔术”告一段落，不过在东部他们仍是比较有实力的球队之一。

　　2000-2001赛季，魔术队得到猛龙队的麦克格雷迪（Tracy McGracy ）以及活塞队的格兰特-希尔（Grant Hill），一举成为东部夺冠呼声最高的球队。遗憾的是身价高达9300万美元的希尔一直饱受踝伤的折磨，几乎断送了球员生涯。魔术队也只能借麦克格雷迪一己之力打拼。虽然麦克格雷迪率领魔术队在2001和2002，连续两年杀入季后赛，但每次都是首轮就被淘汰出局。

　　2002-2003赛季，希尔伤势有所好转，魔术队开局的战绩也不错。麦克格雷迪也仍然保持强劲的攻击力，赛季初屡屡拿下高分。两大巨星与迈克-米勒（Mike Miller）、帕特-加里蒂（Pat Garrity）以及阿姆斯特朗（Darrell Armstrong）组成魔术队的主力阵容。季后得到了肖恩-坎普（Shawn Kemp）也使魔术队实力有所加强，要是希尔贵体无恙的话，魔术队的目标绝不仅仅是季后赛。

　　尽管02和03两个赛季麦蒂均拿下联盟得分王，但由于球队的成绩不佳使得麦蒂彻底失望，球队作出了重大交易，他投奔火箭，魔术则得到弗朗西斯，莫布里和卡托。在交易后，球队成绩仍然毫无起色，04年他们得到状元秀霍华德。

　　在霍华德的前两个赛季，魔术队战绩仍然不佳。06-07赛季，霍华德强力崛起，成为联盟中最有杀伤力的大前锋。

　　2007年夏天，魔术队连出大手笔，先是过亿薪水得到自由球员刘易斯，而后5年8500万续约霍华德，一举成为东部最具竞争力的球队之一，迎来自奥尼尔哈达威解体后奥兰多的最好时刻。

　　08-09赛季，在火箭，魔术，灰熊的三方交易中，拉斐尔-阿尔斯通（Rafer Alston)被交易到奥兰多魔术队，成为魔术队强力的控球后卫。有意思的是，Alston穿上了魔术尘封的1号球衣，麦克格雷迪和“便士”哈达威在魔术效力时穿的都是1号球衣。魔术愈发被人看好。就在选秀大会开始前几个小时篮网和魔术已经达成了一致，篮网已经同意将文斯·卡特和莱恩-安德森送去魔术，换得拉法尔·阿尔斯通，托尼·巴蒂以及考特尼·李。

　　2010年12月19日，奥兰多魔术队与华盛顿奇才队以及菲尼克斯太阳队达成了两笔重磅交易，魔术队用刘易斯从奇才队换来阿里纳斯，再用文斯-卡特，戈塔特，皮特鲁斯，2011年首轮选秀权以及若干现金与太阳交易，换回特克格鲁，以及贾森-理查德森和厄尔-克拉克。魔术队在霍华德赛季报销情况下打进季后赛，在首轮遭遇对手印第安那步行者队，虽然魔术队先赢得首场比赛，但是最后还是不敌步行者队以1-4连两年遭到淘汰。

　　2012年8月11日，奥兰多魔术队通过和掘金队，76人队以及湖人队的四方交易中送出球队的大当家霍华德，霍华德正式宣布成为洛杉矶湖人队一员。在2013年2月21日，魔术队将J·J·雷迪克，伊斯梅尔-史密斯和古斯塔沃-阿永交易到密尔沃基雄鹿队，作为回报，魔术队收到尤德里，托比亚斯-哈里斯。2012-13赛季，魔术队的战绩仅为20-62，是NBA的最差战绩，自2006年以来第一次无缘季后赛。

　　2013-2014赛季，魔术队在2014年NBA选秀选择阿隆-戈登、达里奥-萨里奇。然后换来2017年第一轮选秀权和一个第二轮选秀权换为10号选秀权。2015年2月5日，雅克-沃恩被解除主教练职务，他的总战绩为58胜158负，接替的是临时主教练詹姆斯-博雷戈到球季结束。

　　2014-15赛季，尼克斯队和魔术队这两支在东部联盟战绩倒数的球队交锋，第二节尼克斯20投3中只拿到8分，魔术更是19投3中，只有7分进账，写下联盟自1954-55年开始使用24秒进攻时限以来，两队单节合计得分最低的纪录。而单节7分也也追平魔术单节最低得分纪录，最后尼克斯80-79险胜魔术。2014-2015赛季结束后，在2015年5月29日，宣布前密尔沃基雄鹿队总教教练斯科特-斯凯尔斯担任新任魔术主教练。在2016年5月12日斯凯尔斯辞去了奥兰多魔术队的主教练，成为魔术队史第一位只执教一季就辞职的总教练。

　　2018年4月12日，据著名NBA记者Adrian Wojnarowski爆料，据消息人士透露，魔术已经解雇了主帅沃格尔(Frank Vogel)。在刚刚结束的2017-18常规赛季，魔术仅仅取得了25胜57负的战绩，排名东部第14。沃格尔从上个赛季开始接手魔术，总共执教了164场常规赛，取得了54胜110负的战绩。

　　2018年5月，魔术和斯蒂夫-克里福德签下四年合约，他成为魔术队的新任总教练。