En 1992 il fonde son premier Magic Malik Orchestra qui enregistre la même année sa première maquette qui paraîtra en 1997 sous le titre HWI Project chez Salam Aleikum avec 13 musiciens[1].
Il rencontre ensuite Julien Lourau qui tourne avec sa propre formation : le Groove Gang. En 1998 il participe à l'album City Boom Boom et intègre le Groove Gang. En 1999, Malik accompagne le Groove Gang pour une tournée de plusieurs mois entre l'Amérique du Sud et l'Afrique[1].
En 2000, il décide de se lancer dans un projet d’album sous son nom et reforme un Magic Malik Orchestra. Il enregistre alors l'album 69 96 chez Label Bleu[1].
En 2003 Malik sort son double album intitulé 00-237 XP-1. Le premier disque présente un échantillon de son répertoire dans la lignée de l'album précédent mais plus jazz et plus complexe. Sur le second volume, XP-1, Malik dévoile ses premières tentatives d’échafauder une langue personnelle, cachées derrière le nom de code XP. Steve Coleman, intéressé par la démarche musicale de Malik, apparaît même sur une plage de l'album avant d’inviter Malik à le rejoindre sur l’album On the Rising of the 64 Paths[3].
En 2004, il propose avec le Magic Malik Orchestra un album intitulé 13 XP Song's Book : treize chansons célèbres ou non vues sous le prisme de Malik[3].
En 2008, il sort un nouvel album intitulé Saoule en quintet. Et en 2010 il enregistre pour la première fois en quartet, l'album Short Cuts chez Bee Jazz[4].
En 2017, à la suite d'une rencontre avec le trompettiste Olivier Laisney et le saxophoniste Pascal Mabit, il fonde la Fanfare XP ; un rassemblement d'une quinzaine de musiciens autour d'une charte de composition musicale permettant d'explorer la composition et l’improvisation développés par Malik au cours de sa carrière : taléas-colors (décalages entre des phrases rythmiques et mélodiques), signatures tonales (monde harmonique développé par Malik), modes de Messiaen... Le premier album de la Fanfare XP sort le .
L'originalité de Magic Malik, outre une technique peu commune, est son jeu exubérant et l'utilisation de nombreux cris et chantonnements dans sa flûte, appelé growl. À ce titre, il peut être considéré comme un héritier indirect de Roland Kirk[8],[9].
