Son père est un officier de l'ALN blessé en 1958. Il envoie son fils dès l'âge de neuf ans dans un lycée militaire afin de faire de lui un officier. Mohammed Moulessehoul effectue toutes ses études dans des écoles militaires avant de servir comme officier dans l'armée algérienne pendant 25 ans. {{Référence nécessaire}}
Mohammed Moulessehoul a publié six romans sous son nom de 1984 à 1989 et obtient plusieurs prix littéraires, parmi lesquels celui du Fonds international pour la promotion de la culture (de l'UNESCO) en 1993. Pour échapper au Comité de censure militaire, institué en 1988, il opte pour la clandestinité et publie son roman Le Dingue au bistouri (éditions Laphomic-Alger 1989), le premier dans la série des « Commissaire Llob ». Il écrit pendant onze ans sous différents pseudonymes et collabore à plusieurs journaux algériens et étrangers pour défendre les écrivains algériens. En 1997 paraît en France, chez l'éditeur parisien Baleine, Morituri qui le révèle au grand public.
Il opte définitivement pour le pseudonyme Yasmina Khadra, qui sont les deux prénoms de son épouse, laquelle en porte un troisième, Amel en hommage à Amel Eldjazaïri, petite-fille de l'Emir Abdelkader. Il explique ce choix : {{Citation bloc}}
{{refnec}}
Dans un monde aussi conservateur que le monde arabo-musulman, porter un pseudonyme féminin, pour un homme, est une véritable révolution. Yasmina Khadra n'est pas seulement un nom de romancier, il est aussi un engagement indéfectible pour l'émancipation de la femme musulmane. Il dit à ce propos : {{citation bloc}}
Il fait valoir ses droits à la retraite et quitte l'armée algérienne en 2000 pour se consacrer à l'écriture et ne révèle son identité masculine qu'en 2001 avec la parution de son roman autobiographique L'Écrivain et son identité tout entière dans L'Imposture des mots en 2002. À cette époque ses romans ont déjà touché un grand nombre de lecteurs et de critiques.
À la demande du président Abdelaziz Bouteflika, il est nommé directeur du Centre culturel algérien, fonction à laquelle il est mis fin le 29 mai 2014, après qu'il a parlé « d'absurdité » et de « fuite en avant suicidaire » à propos du quatrième mandat de Bouteflika.
Il acquiert sa renommée internationale avec les romans noirs du commissaire Brahim Llob : Morituri, adapté au cinéma en 2007 par Okacha Touita, Double Blanc et L'Automne des chimères. Llob est un incorruptible, dans un Alger dévoré par le fanatisme et les luttes de pouvoir. Son Algérie saigne à plaies ouvertes et cela révolte le commissaire. Llob n'hésite donc pas à prendre le risque de fouiner dans les hautes sphères de la société, ce qui lui vaut bien vite la sympathie du lecteur. Cette série s'enrichit en 2004 d'un autre roman, La Part du mort.
Khadra illustre également « le dialogue de sourds qui oppose l'Orient et l'Occident » avec les trois romans : Les Hirondelles de Kaboul, qui raconte l'histoire de deux couples afghans sous le régime des Talibans ; L'Attentat, roman dans lequel un médecin arabe, Amine, intégré en Israël, recherche la vérité sur sa femme kamikaze ; Les Sirènes de Bagdad relate le désarroi d'un jeune bédouin irakien poussé à bout par l'accumulation de bavures commises par les troupes américaines.
Yasmina Khadra a touché plusieurs millions de lecteurs dans le monde. Adaptés au cinéma, au théâtre, en bande dessinée, en chorégraphie, ses romans sont traduits dans 42 langues et édités dans plusieurs pays dont l'Albanie, Algérie, Allemagne, Autriche, Brésil, Bulgarie, Corée, Croatie, Danemark, Émirats arabes unis, Estonie, États-Unis, Finlande, Grande-Bretagne, Grèce, Espagne (castillan et catalan), Hongrie, Inde, Indonésie, Iran, Islande, Italie, Israël, Japon, Liban, Lituanie, Macédoine, Norvège, Pays-Bas, Pologne, Portugal, Roumanie, Russie, Serbie, Slovénie, Suède, Suisse, Taïwan, République tchèque, Turquie, Vietnam.
En 2010, Yasmina Kadra dirige une collection sur le Mahgreb chez l’éditeur de polars Après la lune. En 2013, le cinéaste Rachid Bouchareb adapte l'un des romans de Khadra au cinéma sous le titre Enemy Way (La Voie de l'ennemi). Les rôles principaux sont tenus par Forest Whitaker, Harvey Keitel et Ellen Burstyn. En 2013, il fait son entrée dans le dictionnaire (Le Petit Robert des noms propres).