En 1999, le groupe 113 a sorti le single Tonton du bled. Ce morceau racontait avec humour l'histoire d'un adolescent qui doit retourner en Algérie pour les vacances. Mais il n'a pas envie de quitter sa cité, d'aller dans un pays où tout est bancal. Au bout du compte, il s'y rend et parle de finir ses jours là-bas... Ayant connu cette expérience, Djamel Bensalah est allé à la rencontre du 113 pour tenter d'élaborer un projet de long métrage à partir de cette chanson. "Je pensais faire un film qui allait s'appeler Tonton du bled, explique le réalisateur. Mais j'ai vite réalisé qu'avec cette matière, il y avait de quoi écrire une chronique, pas une histoire."
Il était une fois dans l'Oued marque la quatrième collaboration de Djamel Bensalah avec son acteur fétiche Julien Courbey, déjà aux génériques de tous ses précédents films : Y'a du foutage dans l'air, Le Ciel, les oiseaux et... ta mère ! et Le Raid.
"Avec sa tête de fou, ses oreilles décollées, son physique atypique, il faut savoir que c'est une star en banlieue, explique le réalisateur. Mais moi je ne pensais pas spécialement à lui, pas plus qu'à d'autres acteurs de mon entourage d'ailleurs. C'est le groupe 113, quand on a évoqué ce personnage, qui s'est aussitôt exclamé : "Il nous FAUT Julien Courbey !""
Lorsque Djamel Bensalah lui a offert la possibilité d'être l'interprète principal d'Il était une fois dans l'Oued, Julien Courbey s'est d'abord montré méfiant. Il craignait que le personnage de Johnny ne prête à la caricature, "qu'on aille vers un truc "gaguesque" que je ne sentais pas" explique l'acteur. Le scénariste Gilles Laurent et le réalisateur l'ont alors rassuré. "Nous avions la même optique, la même envie d'authenticité. A partir de là, j'ai dit oui", ajoute-t-il.
Après Le Raid, Djamel Bensalah avait envie de retourner à quelque chose de plus simple et de plus ambitieux sur le plan émotionnel. Le réalisateur s'explique : "J'avais envie de remettre l'individu au centre de l'histoire. Comme dans Le Ciel, les oiseaux et... ta mère !, avec ses potes de banlieue, plein de vie et de couleurs. Avec la banane tout le temps. Sans flics, ni embrouilles. Je souhaitais raconter à ceux qui sont prêts à l'entendre que rien n'est inéluctable. Je voulais aider à changer l'image de la banlieue, de l'immigration, et redonner de l'espoir, de la confiance et de la fierté à toute une génération qui en a bien besoin mais ne le réclame pas."
En s'attaquant à la réalisation de cette comédie, Djamel Bensalah avait de nombreuses références en tête, celles du cinéma américain des années 30 à 60, fait par des immigrés européens, notamment Frank Capra. "Mais aussi, d'une certaine manière, Billy Wilder, explique le réalisateur. Quand on pense à Certains l'aiment chaud, c'est quand même l'histoire de gens qui se transforment pour se cacher et qui finissent par se trouver eux-mêmes sous leur déguisement !"
La conception du film s'est faite dans des délais très brefs. "Je suis retourné en Algérie en février 2004 pour la première fois depuis que j'avais douze ans, confie Djamel Bensalah. On a eu l'idée du film en avril. Gaumont a dit oui pendant le Festival de Cannes, le scénario était prêt en juin ; je suis retourné en Algérie en juillet et, en octobre 2004, le film était dans la boîte. Une sorte de coup de poing."
Marilou Berry se souvient d'un petit désaccord qu'elle a eu durant le tournage avec Djamel Bensalah : "Sur la scène dans laquelle je dis à Johnny qu'il est "un seigneur, un seigneur décalé", on était tendu parce que je ne voulais pas donner à Djamel ce qu'il voulait - parce que je n'y arrivais pas, tout simplement, ne voyant pas la scène comme lui... Il a fallu qu'on arrive à s'entendre. Au final, je trouve que tout passe, que c'est touchant, que ce n'est ni ridicule, ni incohérent vis-à-vis du personnage. Après, peut-être que j'essaie de me convaincre !"