Nacido en 1955 en Kednasa, en el Sáhara argelino, hijo de una mujer nómada y un enfermero, oficial del Ejército de Liberación Nacional, en 1964 es matriculado por su padre excombatiente en una academia militar, la Escuela Nacional de los Cadetes de la Revolución. Inicia su actividad literaria pronto, compaginándola con sus estudios y posteriormente su actividad dentro del ejército. Su primera novela, Houria, la acaba en 1973 pero no será publicada sino once años más tarde, en 1984.
En 1989, después de haber publicado seis obras con su nombre real, decide refugiarse bajo un seudónimo para evitar la autocensura que ha marcado sus primeras novelas y poder adentrarse con mayor libertad en la recreación de la Argelia de su tiempo, marcada por el antagonismo entre el gubernamental FLN y el FIS islamista, que pronto dará lugar a una auténtica guerra civil en la que Moulessehoul, como miembro de las fuerzas armadas, combate. El seudónimo lo forman los dos nombres de su esposa. Con él, publica en 1990 El loco del bisturí, una novela policiaca. La obra que le da fama mundial (realmente a su seudónimo, que el público supone que corresponde a una mujer argelina) es Morituri, publicada en París en 1997, a la que siguen otras también publicadas en Francia que se adentran en la crisis argelina: el paro, la corrupción, el islamismo, las diferencias sociales, la ausencia de libertades, la ausencia de perspectivas, el terrorismo, la represión...
En el año 2000 el comandante Moulessehoul abandona el ejército para dedicarse por entero a la literatura; es entonces cuando revela su verdadera identidad, lo que causa gran escándalo tanto en Francia como en Argelia. Quienes habían tenido muy en cuenta en sus críticas el hecho de que estas novelas que tanto éxito cosechaban se debieran a la pluma de nada menos que una mujer de la desgarrada Argelia, caen ahora en la decepción y le acusan de impostura. Su pertenencia a un ejército que en los años inmediatamente anteriores ha sido acusado de perpetrar masacres so pretexto de la lucha contra el terrorismo también le acarrea problemas. Yasmina Khadra contará en una novela, El escritor (2001), los detalles de su vida como escritor dentro del ejército, mientras que en La impostura de las palabras (2002), se enfrentará a todas las acusaciones que se le hacen. Entretanto, Moulessehoul deja su país natal. Tras una corta estancia en México, se instala con esposa y sus hijos en Aix-en-Provence (Francia).
Otro aspecto polémico de su obra es la elección de la lengua francesa. Si bien ésta tiene un amplio uso en Argelia debido al largo tiempo que el país fue colonia francesa, no ha amainado nunca desde la independencia el debate sobre su uso, en clara competencia con el árabe estándar en muchos campos, el de la literatura entre ellos. Moulessehoul explica que él empezó a escribir en árabe, pero que su profesor de lengua criticaba su expresión y le desanimaba, mientras que el profesor de francés hacía justo lo opuesto, lo que finalmente hizo que le fuera más cómodo expresarse en la antigua lengua colonial. No es menos cierto que de haber estado escrita en árabe, la obra de Yasmina Khadra no habría tenido ni mucho menos la proyección internacional que ha logrado.