O grupo, cujo nome foi inspirado no título do conto infantil O Mágico de Oz, do autor estado-unidenseL. Frank Baum, foi fundado em maio de 1989 pelo baterista, Txus. Em sua primeira formação a banda gravou várias demos: Y qué más Da (1989), Canción de Cuna para un Bohemio, e uma terceira demo em 1992. Nesse mesmo ano o grupo foi finalista no Concurso Villa de Madrid, e Chema, o guitarrista decidiu deixar a banda, sendo substituído por Charlie, apelidado de Carlitos.
Depois de duas gravações, a demissão de Charlie e a reentrada de Chema em seu lugar, lançaram seu primeiro álbum Mägo de Oz em 1994, produzido por Txus e Alberto Plaza, que teve vendas escassas e serviu apenas para tornar o grupo um pouco mais conhecido. Neste momento o Mägo de Oz teve uma de suas épocas mais difíceis com o abandono definitivo de Chema e Juanma.[2]
Em 1996, se estabeleceu a formação que perdura quase até a atualidade. Entra José em substituição a Juanma, e Frank substitui Chema. No mesmo ano, começaram a gravar o álbum conceitualJesús de Chamberí, produzido por Alberto Plaza, que foi editado em 1996, e lançado pelo selo Locomotive Music. A turnê deste segundo disco foi chamada de Via Crucis Tour e obteve grande sucesso em toda a Espanha.[3]
Em 1997, decidiram voltar a gravar cinco canções do seu primeiro trabalho, com uma interpretação nova, e notável superioridade na qualidade de som, com os dois novos componentes (Jose e Frank), e produção desta vez realizada por G. Sider. Vale também ressaltar a apresentação do disco na Sala Canciller de Madrid. Mägo de Oz (La Bruja) abriu as portas para importantes festivais e teve maior sucesso que o antecessor. Na temática da imortal obra de Miguel de Cervantes, Dom Quixote, nasce seu terceiro álbum La Leyenda de la Mancha (1998), repleto de riffs de guitarra, melodias célticas, canções marcantes e uma trabalhada produção. A turnê deste disco, The Riiiichal Tour, foi a mais extensa que a banda já havia feito, com 115 concertos.
Com a data do décimo aniversário, a banda decide lançar o vídeo caseiro Resacosix en Hispania (uma paródia de Asterix, o gaulês) que mostraria toda a trajetória do grupo. Logo após juntam-se ao grupo Sergio Kiskilla no teclado e Fernando na flauta transversal, no final de 1999. No mesmo ano, decidiram embarcar em um ambicioso projeto: um álbum duplo, que foi o quarto lançado pelo Mägo de Oz, e se chamou Finisterra.[4]
No ano seguinte lançaram um álbum com composições mais diretas, que incorporariam-se à turnê de Finisterra. Foi chamado Fölktergeist, e com o qual entraram em uma nova turnê muito mais ambiciosa (mais pirotécnica, com melhores cenários e palcos mais detalhados), da qual gravaram um DVD. Foi neste momento que Salva decidiu abandonar o grupo, sendo substituído pelo jovem baixista Sergio.
Em 2003, iniciaram um projeto: realizar três álbuns que comporiam a Trilogia de Gaia: o primeiro com o título Gaia, que foi lançado no mesmo ano. Com a temática de Hernan Cortés e a conquista dos espanhóis aos astecas, dele saíram as pérolas "La Costa del Silencio" e "La Rosa de los Vientos", sendo consideradas grandes composições, inclusive no exterior. Para suportar esse álbum, a banda realizou vários concertos na América do Sul, e as composições envolviam dogmas religiosos, a destruição do planeta e a vingança de Gaia (mãe-terra). Este disco não agradou a alguns de seus fãs, pois tinha mais solos de violino, flauta transversal e menos riffs de guitarra, com uma tendência mais para o hard rock do que para o heavy metal.
Em 2004 a banda volta ao estúdio para gravar o que seria o seu sexto álbum, Belfast, em homenagem à cidade irlandesa de mesmo nome, pois tem sido palco de conflitos religiosos. Neste momento, acontecem importantes mudanças no Mägo de Oz: entra um terceiro guitarrista, Jorge Salán, e meses depois sai Sergio, o baixista.
No ano de 2005 foram lançados mais dois álbuns do Mägo de Oz. O primeiro foi Madrid - Las Ventas. O segundo, lançado em 14 de novembro de 2005, foi Gaia II: La Voz Dormida, editado em sua nova gravadora Dro Atlantic. Traz duras críticas aos governos ditatoriais e à Igreja que oprime e não respeita quem não a segue. Txus e Jose Andrëa fizeram uma participação especial na canção "El Final" no CD Abismos da banda The Garb.
Em 2006, foi lançado o single "Hoy Toca Ser Feliz", mostrando um som da banda mais versátil e com arranjos marcantes. Contém também extras que incluem uma gravação da canção "Memoria da Noite" do grupo Luar na Lubre e um videoclipe. Em 5 de dezembro de 2006 a banda lançou o álbum duplo de compilações "Rock N' Oz", incluindo regravações de "Molinos de Viento, "Jesús de Chamberí", "Hasta Que Tu Muerte Nos Separe" e "El Cantar de la Luna Oscura".
Em 2 de novembro de 2007, é lançado o álbum "La Ciudad de Los Árboles", surpreendendo aqueles que esperavam pelo lançamento de um "Gaia III". Também é previsto para abril de 2008 o começo da turnê "Borriquito como Tour 2008".
Em 6 de abril de 2010 é publicado o terceiro disco da trilogia Gaia, o disco Gaia III: Atlantia com o primeiro single 'Que el viento sople a tu favor', esse disco foi considerado um dos mais trabalhados, e onde a banda inovou com a mescla de alguns gêneros, como no caso esse disco passou a ter um toque mais 'eletrônico' é bem notável nas músicas Dies Irae, Für immer e na própria música Atlantia.
Em Julho de 2010 o flautista Fernando Ponce de León deixa a banda por motivos pessoais, e no final do mesmo mês Josema passa a ser o novo flautista da banda. No dia 30 de novembro de 2010, no mesmo ano que foi lançado o disco Gaia III, a banda lançou o disco Gaia Epilogo que contém músicas recicladas que ficaram de fora por algum motivo dos 3 discos da trilogia Gaia.
Dia 24 de outubro de 2011 o vocalista José Andrea anuncia sua saída da banda. José Andrea e Mago de Oz, por acordo, de forma amigável, decidimos quebrar nossa relação artística e terminar uma etapa onde se pode apreciar uma das vozes mais mágicas dos últimos 15 anos no rock espanhol. Tanto José Andrea quanto o resto da banda achamos que ele merecia adeus a você da melhor maneira que ele pode fazer: dar-nos a sua voz em concertos recentes. Assim, confirmam que, neste, o nosso site oficial, tanto a turnê norte-americana como datas agendadas em Espanha será o seu último concerto antes de deixar a banda. Gostaríamos de desejar a todos boa sorte em sua futura vida profissional e pessoal longe da estrada de tijolos amarelos. Obrigado por deixar a pele e voz ao longo dos anos. "Devemos estar sobre o arco-íris ..." Oficial comunicado Mágico de Oz, 2011.[5]
Em 11 de novembro de 2011 é anunciado o novo disco recopilado com as principais baladas da banda e com 2 novas músicas. Esse foi o último disco da banda com José Andrea. José Andrea então fez seus últimos concertos como vocalista do Mago de Oz pela América latina no final de novembro e na primeira quinzena de dezembro, e na Espanha nos últimos dias do ano, por problemas vocais que houve em alguns concertos a data foi transferida para o final de dezembro, sendo assim a 'era José Andrea' termina dia 30 de dezembro de 2011 com o último concerto na Sala la Riviera em Madrid.
Em 11 de abril de 2012 é anunciado na rádio Mariskalrock a saída do baixista Peri e do tecladista Sérgio Kriskilla para seguir na banda de Uróboros de José Andrea. No dia 30 de maio a banda criou um Casting para buscar um novo vocalista, pouco tempo depois foi anunciado o baixo do Mago de Oz Fernando Mainer de Tako, baixista de Jorge Salán e de Jeff Scott Soto e também se integrou a banda o tecladista Javi Diez que também é da atual banda paralela de Txus de Fellatio a Burdel King.
Dia 8 de agosto de 2012 por fim é anunciado o tão esperado vocalista, Zeta foi apresentado como substituto de José Andrea e novo vocalista da banda Mago de Oz, no mesmo dia foi apresentado as gravações enviadas para o casting da banda. No dia 10 de outubro Txus em uma entrevista a Rafabasa.com confirmou que dia 27 de novembro será lançado o novo disco que não foi revelado ainda seu nome, mas também será apresentado um single no dia 31 de outubro com a música Xanandra, também no mesmo dia será lançado o seu vídeo clipe.
Dia 27 de novembro de 2012 por fim é lançado o novo disco Hechizos, Pócimas y Bujería com o novo vocalista Zeta, um disco com músicas mais 'heavy' se destacando mais nas guitarras e com menos teclados. Nele encontramos uma música polêmica que se chama 'H2Oz' e sua letra diz que a banda não morreu e que o antigo vocalista não fará nenhuma falta. Também encontramos no disco grandes músicas como Satanael, Mercado de Brujas, Brujas (cantada por Patricia Tapia), o single Xanandra e a música do mesmo nome do disco 'Hechízos, Pócimas y Brujeria.
Em fevereiro de 2013 a banda começa sua turnê, começando pelo continente Americano em Guatemala.[carece de fontes?] Em dezembro do mesmo ano é lançado Celtic Land, álbum duplo que celebra os 25 anos de banda.[6][7]
