Khaled Hadj Brahim, alias Khaled est né dans un faubourg d'Oran à Sidi El Houari le 29 février 1960. Son père travaille dans le garage de la police, recevant un modeste salaire. Tout petit, le jeune Khaled tombe dans la magie musicale et écoute beaucoup de musique marocaine, ainsi que les chanteurs Elvis Presley et Johnny Hallyday. Vers l'âge de sept ou huit ans, il a trouvé sa voie. Mais dans sa famille, personne n'est musicien, hormis son oncle paternel qui joue de l'accordéon. Son père quant à lui n'apprécie pas les incartades de son fils et le corrige quand celui-ci fait les quatre cents coups : à 14 ans, il est renvoyé de l'école pour absences répétées. En effet, à cette période, il chante dans les mariages et les cabarets à l'insu de son père avec son groupe les "Cinq Etoiles".
En 1974, c'est son premier enregistrement sur un magnétophone deux pistes "Trig El Lici", qui sort en 45 tours et passe inlassablement sur les radios. Le public accroche tout de suite. Cheb (le jeune) Khaled comme on le nomme à Oran, ne touche pas un sou de ce succès. Pour gagner sa vie, il est amené à faire divers métiers, garçon de café, cordonnier, etc..
