Orlando Magic to jeden z najmłodszych klubów NBA. Do ligi dołączyli w roku 1989, razem z Charlotte Hornets, Miami Heat i Minnesota Timberwolves. Nazwa "Magic" została wybrana spośród 4,296 zgłoszonych opcji, a w ścisłym finale "pokonała" takie alternatywy jak "Heat", "Tropics" i "Juice". Początki były trudne. W swoim pierwszym sezonie Magic zanotowali bilans 18-64, a gwiazdami drużyny byli Nick Anderson czy Scott Skiles, który w barwach Magic w 1990 roku zaliczył rekordową ilość 30 asyst w jednym meczu. Skiles był pierwszym nagrodzonym zawodnikiem z Orlando, zdobywając tytuł Most Improved Player za sezon 1990/91. W drugim sezonie było już nieco lepiej. Magic zakończyli go z bilansem 31-51, a na 40 z 41 rozegranych w Orlando spotkań sprzedano wszystkie bilety. Punktem zwrotnym w historii klubu był Draft w 1992 roku, kiedy Magic wybrali z numerem pierwszym centra Shaquille'a O'Neala. Nie udało się jednak awansować od razu do Play-Off. Rok później Magic z nowym trenerem, Brianem Hillem, wybrali w Drafcie Chrisa Webbera, ale oddali go do Golden State Warriors za Anfernee "Penny'ego" Hardawaya. Shaq i Penny stali się jednym z najlepszych duetów NBA. W swoim debiucie w Play-Off odpadli jednak w pierwszej rundzie z Indianą Pacers. W sezonie 1994/95 po raz pierwszy wygrali swoją dywizję, kończąc rok z bilansem 57-25. Wtedy też po raz pierwszy awansowali do finałów NBA, przegrywając w nich jednak z Houston Rockets 0-4. Rok później, mimo jeszcze lepszego bilansu w sezonie zasadniczym (60-22), Magic odpdali wcześniej, w finale konferencji, przegrywając z fenomenalnymi Chicago Bulls. Po odejściu O'Neala do Los Angeles Lakers drużyna z często kontuzjowanym Hardawayem tułała się mniej więcej w środku tabeli. W sezonie 1999 powrócili na szczyt konferencji wchodniej, ale tylko w sezonie zasadniczym. W pierwszej rundzie PO odpadli z Philadelphią 76ers i generalny menadżer John Gabriel sprzedał Hardawaya do Phoenix Suns. W 2000 roku, dysponując ogromnym budżetem, Magic ściągnęli do siebie Granta Hilla i Tracy'ego McGrady'ego. O ile z powodu wiecznych kontuzji transfer Hilla okazał się niewypałem, o tyle McGrady po odejściu z Toronto Raptors rozwinął skrzydła i stał się supergwiazdą i jednym z najlepszych strzelców ligi, wprowadzając Orlando do Play-Offów 3 lata z rzędu - za każdym razem odpadając jednak już w pierwszej rundzie. Po tragicznym sezonie 2003/04, w którym Magic byli najgorsi w lidze, z drużyny za wszelką cenę chciał odejść Tracy McGrady. Drużyna popadła w przeciętność aż do roku 2007. Wtedy to do rozwijających się Dwighta Howarda, Hedo Turkoglu i Jameera Nelsona dołączył Rashard Lewis, a na ławce trenerskiej zasiadł Stan Van Gundy. W 2008 roku przygodę w PO zakończyli na drugiej rundzie, ale już rok później, w dwudziestą rocznicę istnienia, awansowali po raz drugi w swojej historii do finałów, gdzie przegrali z Los Angeles Lakers. Świadomi braku strzelca mogącego wziąć na swoje barki ciężar gry w najważniejszych minutach, przed sezonem 2009/10 Orlando Magic postanowili ściągnąć z New Jersey Nets Vince'a Cartera. Vince nie spełnił jednak w 100% oczekiwań. Orlando po fantastycznej grze w drugiej połowie sezonu wygrało dywizję i z 2 miejsca weszło do Play-Off, gdzie w 2 pierwszych rundach bez problemu pokonało rywali. W Finale Konferencji nie sprostali jednak Boston Celtics.