Issue du conservatoire national d'Art dramatique de Paris, Cylia Malki fait ses premiers pas au cinéma en 1998 aux côtés de Romain Duris et Benoît Magimel dans Dejà mort, un film de Olivier Dahan, histoire d'une jeune femme plongée dans le sombre milieu du porno. L'année suivante, elle joue la soeur marginale d'Elie Kakou dans la comédie douce amère de Olivier Schatzky: Monsieur Naphtali.

En 2000, elle interprête une jeune immigrée faisant partie de l'équipe de nettoyage de Muriel Robin dans le drame social de Mehdi Charef: Marie-Line. Après une courte apparition dans Les Morsures de l'aube (Antoine de Caunes, 2000), elle retrouve Olivier Dahan avec Le Petit Poucet (2001), dans lequel elle joue le bras droit de Jambe de fer.

En 2002, Cylia Malki tourne à nouveau sous la direction de Medhi Charef en obtenant le premier rôle de La Fille de Keltoum, film qui retrace le parcours d'une jeune fille de dix neuf ans débarquant en plein désert algérien pour retrouver ses parents.

En tournant Violence des échanges en milieu tempéré de Jean-Marc Moutout en 2003, elle se révèle comme une actrice sensible, interprétant le rôle d'une mère célibataire.

Elle est Samira dans La Moustache d'Emmanuel Carrère.