Chronique d'une rencontre entre deux existences cabossées sur fond de milieu carcéral, Graziella dépeint un univers que le réalisateur connaît bien puisqu'il est intervenu durant un an dans une prison du Val d'Oise où il animait des ateliers d'écriture de scénarios pour des détenus.
Seize ans après avoir donné son premier rôle dramatique à Muriel Robin dans Marie-Line, Mehdi Charef remet ça avec une comédienne fantasque habituée des comédies, l'Espagnole Rossy De Palma. Celle qui demeure comme étant l'une des actrices fétiches de Pedro Almodovar fut le premier choix du cinéaste pour le rôle de Graziella, comme l'explique la productrice du film Michèle Ray-Gavras : "Il a écrit le rôle pour Rossy."
Cinéaste empreint d'un style naturaliste, Mehdi Charef avait déjà évoqué dans ses précédents films, des sujets sociétaux tels que la vie dans une cité avec Le Thé au harem d'Archimède ou le quotidien de femmes de ménage dans Marie-Line. Avec Graziella, il s'empare d'un autre fait sociétal, à savoir le quotidien de deux détenus et leurs rapports avec le monde extérieur. Sur la question du cinéma et ses rapports avec le réel, le réalisateur déclare ceci : "On croit que c'est de la fiction, mais c'est finalement des choses vécues, entendues, mais après il faut que cela redevienne de la fiction."
Avec Graziella, Mehdi Charef collabore pour la cinquième fois avec la productrice Michèle Ray-Gavras, qui avait déjà produit Le Thé au harem d'Archimède, Miss Mona, Camomille et Cartouches Gauloises. Productrice de talent, elle est en outre la femme du réalisateur Costa-Gavras, à l'origine du passage au cinéma de Mehdi Charef puisque c'est lui qui l'a conseillée d'adapter sur grand écran son roman "Le Thé au harem d'Archimède".
Si Graziella marque la première collaboration entre Rossy De Palma et Mehdi Charef, ce dernier retrouve pourtant ici deux actrices qu'il a déjà dirigées, Claire Nebout et Philippine-Leroy Beaulieu. Il avait travaillé avec la première sur Au pays des Juliets en 1992 tandis que la seconde tenait le rôle principal de son film Camomille en 1987.
Société de production créée par Costa-Gavras et Michèle Ray-Gavras, KG Productions a produit la majorité des films de Mehdi Charef. Avec Graziella, la société, ayant déjà accompagné les films de cinéastes comme Tony Gatlif, René Clément ou Pierre-Granier Deferre, ajoute une corde à son arc puisque désormais elle fera également office de distributeur. Un choix qui s'explique par la conjoncture actuelle du marché du cinéma français où la distribution d'un film indépendant comme Graziella est synonyme d'une prise de risque pour les petits et moyens distributeurs. C'est pour éviter ce genre de cas que KG Productions se lance dans la distribution.
Graziella a été sélectionné dans différents festivals parmi lesquels les dernières éditions du Festival du film français de Malaga ainsi que le Festival international du film d'amour de Mons.