Dès l’époque d'Indigènes et la rencontre d'anciens combattants d'Afrique du Nord ou d'Afrique noire, Rachid Bouchareb et son coscénariste Olivier Lorelle se sont rendus compte qu’il y avait chez ces vétérans une profonde déception et amertume vis-à-vis de la France. Du coup, la fin de la guerre et la Libération ont relancé le mouvement de la décolonisation. C’est à ce moment-là qu’est né Hors-la-loi.
Le réalisateur d'origine algérienne Rachid Bouchareb a toujours eu à cœur de traiter l'Histoire qui lie la France et l'Algérie à travers une grande fresque cinématographique, un peu comme avait pu le faire Sergio Leone avec Il était une fois en Amérique. En 2006, Indigènes amorce ce travail de mémoire par la Seconde guerre mondiale, suivi en 2010 par Hors-la-loi, qui commence par la guerre d'Algérie. Un troisième épisode devrait conclure portant sur l'intégration en métropole après 1962.
Dans une première version du scénario d'Indigènes, le film devait se terminer par le massacre de Sétif du 8 mai 1945. Mais Rachid Bouchareb changea finalement d'idée : "Je me suis dit qu’il fallait que la dernière scène se déroule en France". En 2010, cet événement tragique sur le sol algérien ouvre le long métrage Hors-la-loi.
Sorti en 2010, Hors-la-loi est le premier film abordant directement les massacres de Sétif en 1945 où des manifestations pacifiques indépendantistes algériennes ont été sévèrement réprimées par l'armée française. A sa présentation au Festival de Cannes, une polémique éclata, portée par le député Lionnel Luca. Soutenu par des associations de pied-noirs, l'élu attaqua le regard que portait le film sur ces tragiques évènements, sans pour autant l'avoir vu, et le fait qu'Hors-la-loi soit présenté comme un film algérien alors qu'il était, en majorité, financé par la France.
Rachid Bouchareb a construit son film comme une fresque parcourant quarante ans d’histoire, avec de grands décors, des séquences d’action, et des costumes minutieusement travaillés : "J'ai imaginé des personnages qui gèrent la révolution comme Al Pacino gère la famille et les affaires dans Le Parrain de Coppola. J'ai d'ailleurs repensé à des films que j'adore comme Il était une fois en Amérique de Sergio Leone, Viva Zapata ! d'Elia Kazan ou Le Vent se lève de Ken Loach".
Comme Indigènes, Hors-la-loi a demandé un an de préparation, afin de mettre au point les principaux paramètres de la fabrication du film et pour que chacun comprenne dans quelle direction Rachid Bouchareb voulait aller : "On a pris le temps d’aller à Sétif pour y retrouver des éléments de décors, comme le Café de Paris, la rue principale et les faubourgs. De même, on s’est beaucoup documenté sur le Pigalle des années 50", explique le cinéaste.
Pendant la préparation, l'équipe technique a pris conscience que Hors-la-loi ne pouvait être qu’un film de studio, impliquant des choix esthétiques précis qui ont été opérés avec le chef-opérateur Christophe Beaucarne. Près de 90% du film a été tourné dans les studios tunisiens de Tarak Ben Ammar, où a été reconstruit les rues de Sétif, le bidonville, Pigalle ou les intérieurs – la salle de boxe ou les appartements. Le tournage a duré cinq mois et demi.
Hors-la-loi a été tourné en grande partie dans les studios Tarak Ben Ammar, situés à Ben Arous en Tunisie. Les tournages de grands films hollywoodiens comme La Guerre des étoiles (1977), Les Aventuriers de l'Arche perdue (1981) ou encore Le Patient anglais (1996) d'Anthony Minghella s'y sont déroulés.
Pendant leurs recherches, Rachid Bouchareb et le scénariste Olivier Lorelle ont rencontré un faussaire français qui, durant l'Occupation, fabriquait de faux papiers pour les résistants français, et qui a poursuivi son activité dans les années 1954-55 – au bénéfice, cette fois, de la résistance algérienne. Il trouvait qu’il servait, à chaque fois, une cause juste. De plus, quand le réalisateur a rencontré à Alger un ancien membre de la Fédération de France du FLN qui devait exécuter les traîtres à la cause – et qui en souffre encore aujourd’hui –, "L' Armée des Ombres [lui] est revenu en tête. Une dizaine d’années après l’Occupation, on se retrouvait à Paris dans la même ambiance que dans le film de Jean-Pierre Melville", commente-t-il.
Les rôles que tiennent Jamel Debbouze (Saïd), Roschdy Zem (Messaoud) et Sami Bouajila (Abdelkader) dans Hors-la-loi portent les mêmes prénoms que ceux qu'ils incarnaient dans Indigènes, quatre ans plus tôt. Mais il ne s'agit pas des mêmes personnages d'un film à l'autre.
"Les Français, les Algériens, les Maghrébins et les Africains, surtout les nouvelles générations, ont besoin de connaitre le passé colonial", explique Rachid Bouchareb. "C’est aussi le rôle du cinéma. Mais encore une fois, le spectateur veut aller au cinéma, pas lire un livre d’histoire. Il faut lui raconter une histoire. En sortant de la salle, à lui, s’il en a le désir, d’aller consulter les ouvrages d’histoire. Le film peut permettre un débat d’idées avec tous les points de vue. Ceux qui ont été au centre des événements ont leur mot à dire et il y encore qui demandent à raconter leur histoire dans la grande Histoire. Ils sont la mémoire vivante".