Abd al Malik naît Régis Fayette-Mikano le 14 mars 1975 à Paris, de parents congolais. Après quatre années passées à Brazzaville, la famille revient en France en 1981 pour s’installer à Strasbourg, dans le quartier du Neuhoff. Son adolescence est marquée par des actes de délinquance mais avide de savoir, il se montre bon élève à l'école. En quête de repères, son besoin de spiritualité le mène vers l’islam auquel il se convertit à 16 ans et devient Abd al Malik.

Il fonde rapidement avec cinq autres garçons de son quartier un groupe de rap, les New African Poets (NAP). "Trop beau pour être vrai", leur premier maxi autoproduit, sort en 1994. Après un album mort-né qu’ils ne parviennent pas à commercialiser, ils ne se découragent pas et leur effort se concrétise en 1996 avec "La Racaille sort un disque". Le bon accueil qui lui est réservé lance la carrière de NAP qui enchaîne en 1998 avec "La Fin du monde". Quelques-uns des plus grands noms du rap français sont invités : Faf La Rage, Shurik’n (IAM), Rocca (La Cliqua), Rockin’s Squat (Assassin).

Un troisième album, "A l’intérieur de nous", parait deux ans plus tard. La musique n’a pas détourné Abd al Malik de ses études qu’il mène de front jusqu’à la licence, suivant à l’université un double cursus de lettres classiques et de philosophie. Alors qu’il avait flirté un moment avec l’extrémisme sur le plan religieux, il a enfin trouvé ce qu’il cherchait dans la voie soufi au contact du sheikh marocain Sidi Hamza al Qâdiri Boutchichi qui devient son maître spirituel.

En 1999, il se marie avec la chanteuse r'n'b franco-marocaine Wallen. Naît de leur union un petit garçon en 2001, prénommé Muhammed.

En mars 2004, Abd al Malik sort son premier album solo, "Le Face à face des cœurs", qu’il définit comme "un rendez-vous galant avec soi-même " et dont le titre fait référence à un ouvrage de l'intellectuel soufiste Faouzi Skali. Les quinze morceaux "audacieusement romantiques " sont précédés par une courte interview, dirigée par la journaliste Pascale Clark, qui permet à l’artiste de présenter sa démarche. Aïssa, de NAP, participe à la plupart des morceaux. Parmi les autres invités figurent Marco Prince, Souad Massi et Wallen (son épouse, chanteuse de R&B). La dernière chanson, "Que Dieu bénisse la France", avec Ariel Wizman, fait écho au livre que sort le rappeur simultanément, "Qu’Allah bénisse la France", dans lequel il explique son cheminement personnel et défend une conception d’un islam tolérant. L’ouvrage est récompensé en Belgique par le prix Laurence-Trân.

A Bruxelles, la même année, le jeune homme découvre le slam au cours d’une session organisée par une association qui l’a invité. Séduit, il se promet d’intégrer cet élément à sa démarche artistique future.

L’album qui paraît en juin 2006 est très éloigné du précédent. Pour concevoir "Gibraltar", il lui a fallu déconstruire dans la forme la notion même de rap, tout en restant hip hop. Ce à quoi il aboutit ne ressemble à rien d’autre : alliant la chanson, le jazz, le slam et le rap, ses morceaux ont une esthétique nouvelle. Si Bilal, membre du groupe NAP, signe la plupart des compositions, le pianiste Gérard Jouannest écrit trois pièces pour le rappeur. L’idée d’entrer en contact avec le pianiste de Brel lui vient en le voyant dans un reportage télévisé. Tout en restant passionné par le rap, il s’est mis à écouter Brel attentivement depuis une dizaine d’années, frappé par sa force d’interprétation. Dès la première rencontre entre les deux hommes, le courant passe et Abd al Malik se met aussitôt à écrire en écoutant le pianiste jouer. D’autres musiciens d’horizons aussi peu habituels sur un disque de rap sont venus participer au projet : le bassiste Laurent Vernerey, l’accordéoniste Marcel Azzola ou encore le batteur Régis Ceccarelli, impliqué dans l’instrumentation des morceaux et dans le choix des samples provenant d’univers très variés (Keren Ann, Nina Simone, Fairuz…). Grâce à cette construction musicale, la poésie qui émane des textes n’en devient que plus prenante.

Après "12 septembre 2001", premier extrait de l’album, un second simple sort en novembre 2006 : "Les Autres" est en fait une version revisitée de "Ces gens-là", de Jacques Brel.

Disque d’or en décembre 2006, puis double Disque d’or en mars 2007, "Gibraltar" est plus qu’un succès commercial : après le Prix Constantin et le Prix de l’Académie Charles-Cros en 2006, l’album continue sa moisson en 2007 avec la Victoire de la musique dans la catégorie “musiques urbaines” et le Prix Raoul-Breton décerné par la Sacem.

En février 2007, avec un quatuor jazz comprenant notamment Laurent De Wilde, Abd al Malik démarre une tournée qui va durer près de treize mois pour plus de cent concerts en France, en Belgique, en Suisse et au Canada ! Du Printemps de Bourges aux Francofolies (de La Rochelle, de Spa et de Montréal), en passant par Montreux, les Eurockéennes ou Musiques métisses, il aura participé aux principaux festivals. En mars, il passe à Paris à la Cigale puis au Cirque d’Hiver.

Juin 2007