Hadj BrahimChebKhaled est né le 29 février 1960, dans le quartier Elkmine de Sidi El Houari, bourg situé dans la banlieue d’Oran (Algérie). Ses parents sont originaires d’un village dépendant de la division administrative de Mostaganem. C’est du balcon de la mairie de cette ville que le Général de Gaulle lancera le désormais historique : « Vive l’Algérie française ! »
Il suffit du soleil, c’est tout de suite la musique
Même si sa famille ne l’incite pas à les pratiquer (seul un vague oncle joue de l’accordéon), le jeune (Cheb) Khaled écoute, dès sa prime enfance, beaucoup de musiques, en provenance d’Egypte (il s’imprègnera de l’art de Farid el-Atrache, et la diva Oum Kalsoum aura naturellement une profonde influence sur lui), d’Espagne ou de France (qui pouvait échapper à cette époque à Johnny Hallyday ?). De la musique anglo-saxonne, il retiendra plus tard James Brown, Elvis Presley, ou les Beatles. Mais ses influences sont également typiquement algériennes (Ahmed Wahby), voire franchement oranaises (en la personne du chantre de la musique de la ville, Blaoui El Houari).
Déjà fin lettré, Khaled se passionnera également pour l’œuvre de Mostefa Ben Brahim, qui compile les destinées de combattant émérite de l’indépendance algérienne, et de poète reconnu comme une gloire nationale. Néanmoins, il serait injuste de passer sous silence le formateur le plus déterminant du jeune homme : Cheikh Fethi, de trois ans l’aîné de Khaled, fut son compagnon de prime enfance et d’adolescence, et un chanteur à la carrière aussi étincelante qu’injustement interrompue de manière prématurée par la maladie. Initiateur de la lignée du raï oranais, il aura une incontestable influence sur Khaled. Dès l’âge de neuf ans, Khaled intègre (à l’insu de sa famille) le groupe phare de sa ville, Les Cinq Etoiles. De plus, la future vedette apprend guitare, piano, flûte et accordéon à l’école, qu’il quitte dès seize ans, convaincu que son destin passe par une carrière dans la chanson. Son père, policier travaillant dans le garage automobile du commissariat, et ne percevant qu’un modeste salaire, voit d’un œil sévère ce choix risqué. L’exclusion temporaire de Khaled de l’école pour absences répétées lui vaudra d’ailleurs une sévère correction de la part de son géniteur.
Dès 1974, il parvient, tout en se produisant régulièrement dans les cabarets oranais (même s’il survit essentiellement grâce à des petits boulots, et autres expédients), à enregistrer son premier 45 tours (« Trig el lici » / « La Route du Lycée », ou les joies de l’école buissonnière et coquine). Le disque fait parler de lui, mais ne rapporte rien à Khaled si ce n’est une renommée naissante, et il ne survit que grâce à des emplois de garçon de café, ou de cireur de chaussures. Il se produit de façon systématique dans les cérémonies de mariage ou de circoncision, et les lieux de plaisir de la côte, où il parfait son métier. Mais on ne l’entend jamais à la radio : y chanter les filles et l’alcool est interdit. Deux années plus tard, « El Marsam » est sa première chanson à recueillir un important succès à travers tout le pays. Sa voix puissante fait merveille dans cet appel à l’amour, et aux plaisirs charnels. Khaled prend alors une décision faussement anecdotique, en remplaçant dans son orchestre violons par guitares électriques. Il devient dès cet instant le chouchou des enfants de l’intelligentsia algérienne, tous caciques du FLN désormais aux commandes du pays.
Dès 1982, grâce à l’adjonction de claviers électroniques, son orchestre adopte désormais une configuration occidentale. Khaled vend énormément de cassettes audio, tant dans son pays que parmi la diaspora algérienne, et ce support, piraté naturellement dans tout le Maghreb, lui fait perdre un nombre conséquent de royalties : d’Oran à Barbés, c’est l’habituel pont de contrefaçons qui se met en place. En tout état de cause, les enregistrements se succèdent de manière vertigineuse, souvent peu ou pas préparés, bâtis sur des paroles parfois improvisées, mais alimentant les poches systématiquement percées du chanteur. Il participe en 1985 au premier Festival Raï d’Oran (dont il remporte le premier prix) : le pouvoir politique s’est résolu à tenter de récupérer un mouvement musical, et culturel, inexorable.