Fellag è nato ad Azeffoun, in Cabilia (una regione dell'Algeria settentrionale), il 31 marzo del 1950 da una famiglia berbera. Ha studiato teatro presso l'Istituto Nazionale di Arte Drammatica e coreografia dell'Algeria a Bordj El Kiffan, dal 1968 al 1972; le sue prime recite nei teatri algerini risalgono al 1970.
Dal 1978 al 1981 ha vissuto in Francia e in Canada, vivendo di piccoli lavori e rimandando la realizzazione dei suoi progetti artistici. Nel settembre 1985, tornato in Algeria, è stato assunto dal Teatro Nazionale algerino, dove ha lavorato come attore e regista. Nel 1987 crea il suo primo spettacolo, Le avventure di Tchop. Nel settembre 1993 è stato nominato direttore del teatro di Béjaïa.
Dotato di un grande umorismo, i suoi spettacoli sono prevalentemente comici ma ricchi di ironia intelligente e di critica di costume. Anche nei suoi romanzi riesce ad affrontare con leggerezza e profondità temi importanti come quelli dell'integrazione degli immigrati (Rue des petites daurades) e la stagione del terrorismo islamista in Algeria (L'Allumeur de rêves berbères).
Sposatosi a 40 anni, ora vive con l'attrice Marianne Epin.
Spettacoli
1987: Les Aventures de Tchop (Le avventure di Tchop), Algeri
1989: Cocktail Khorotov (spettacolo in dialetto algerino), Petit Théâtre, Algeri.
Balcone di Djamila
1990: Labès SOS .
1991: Un bateau pour l'Australie (Una barca per l'Australia), che è stato trasformato in un DVD nel 2002.
1994: Delirium, Tunisi.
1997: Djurdjurassique Bled, internazionale teatro di lingua francese a Parigi.
2001: Rue des petites daurades (Via delle piccole orate), Théâtre international de langue française, Parigi.
2002: Le Syndrome de la page 12 (La sindrome della pagina 12), Théâtre du Rond-Point, Parigi.
2003: Che bella la vita !, Théâtre international de langue française, Parigi.
2003: Opéra d'Casbah, « mise en images » Jérôme Savary, con Fellag, Biyouna, Abdou Elaïdi, un'orchestre arabo-andalusa e dei ballerini; Espace Saint-Jean (sous chapiteau), Marsiglia.
2008: Tous les Algériens sont des mécaniciens (Tutti gli algerini sono dei meccanici), regia di Marianne Épin e l'autore, Les Nuits de Fourvière, Lione.
Olivier Mongin, in De quoi rions-nous ? Notre société et ses comiques, Plon, 2006, consacra un capitolo a Fellag ed alla sua arte : Fellag, l'entrechoquement des langues et des identités
