Hors-la-loi raconte l'histoire de trois frères sur fond de guerre d'Algérie, entre 1945 et 1962. Le film s'ouvre sur les massacres de Sétif, le 8 mai 1945 : le défilé qui fête la victoire des Alliés tourne à l'émeute entre Algériens et Européens alors que les nationalistes font valoir leurs revendications.

Un collectif nommé "Vérité Histoire - Cannes 2010" appelle sur un site Internet proche de l'extrême droite à manifester à Cannes et à "pourrir" le Festival, qui aura lieu du 12 au 23 mai.

Les historiens sont convoqués à un débat qui n'est pas abordé à l'écran, à savoir le nombre de victimes côtés européen et algérien. "Le premier mort de Sétif, c'est un Algérien. Il brandissait le drapeau (algérien) dans le cortège, et un commissaire de police lui a tiré une balle dans la tête", rappelle l'historien Benjamin Stora.
Hors-la-loi est la suite du précédent film de Rachid Bouchareb, Indigènes, lequel rendait hommage aux tirailleurs algériens qui se sont battus pour libérer la France, pendant la seconde guerre mondiale. Sélectionné à Cannes en 2006, Indigènes avait valu à ses cinq principaux interprètes - Jamel Debbouze, Roschdy Zem, Samy Naceri, Sami Bouajila et Bernard Blancan - le prix collectif d'interprétation masculine.