La Trahison est l'adaptation du roman homonyme de Claude Sales, publié en 1989. Il s'agit d'un récit autobiographique, l'auteur ayant été aspirant puis sous-lieutenant en Algérie de juin 1958 à décembre 1959. Sales, qui a participé avec le réalisateur à l'adaptation de son roman (il a même assisté au tournage durant quelques jours), a jugé le film fidèle à l'oeuvre d'origine : "L'histoire, les personnages, le climat, la méfiance et la tension qui régnaient alors ; le regard absent des femmes, buté des hommes ; l'innocence des enfants ; ma stupéfaction à l'annonce de ce qui se préparait ; tout, tout est vrai. Je ratifie et j'admire le travail de Philippe Faucon, même si le film et le livre sont différents."
Le souhait de Philippe Faucon de réaliser un film sur la guerre d'Algérie est lié à son histoire familiale. Né à Oujda, au Maroc, près de la frontière algérienne, le cinéaste confie : "Ma mère est née à Maghnia, de l'autre côté de la frontière, en Algérie donc (...) Et des deux côtés de la frontière, c'est une région minière. Mon grand-père maternel se déplaçait avec sa nombreuse famille, d'un côté ou de l'autre de la frontière, suivant les offres d'embauche. En Algérie, il y avait la guerre, et ma mère m'a raconté que je suis né au 2e étage d'un hôpital ; tandis qu'au 1er étaient soignés des combattants indépendantistes algériens, qui avaient été blessés dans des accrochages en Algérie, et ramenés au Maroc pour être soignés à Oujda. L'entrée de l'hôpital était gardée par des soldats de l'A.L.N. (Armée de Libération Nationale) en armes, que mon père croisait lorsqu'il venait, en uniforme de l'armée française, rendre visite à ma mère. Le Maroc était indépendant depuis deux ans, il y restait quelques personnels administratifs et militaires français, dont mon père ; et sur place, dans cet hôpital, il y avait ainsi une sorte de statu quo établi par les autorités marocaines. Ensuite, mon père a été envoyé à Alger, où mes parents ont vécu les six derniers mois de la guerre. Bien que très petit, j'ai l'impression d'avoir le souvenir de la tension, de la peur qui régnaient."
Le casting mêle acteurs expérimentés et non-professionnels. On retrouve ainsi Vincent Martinez (frère d'Olivier), remarqué dans L'Ecole de la chair et La Confusion des genres, Cyril Troley, le héros de Paria de Nicolas Klotz (2001) et Luc Thuillier, vu dans Monsieur Hire et La Vieille qui marchait dans la mer. Taïeb, en revanche, est interprété par Ahmed Berrhama, qui ne se destinait pas à jouer la comédie, comme l'explique le réalisateur : "(...) un jour, à l'aéroport d'Alger, en descendant de l'avion, j'ai rencontré Ahmed qui venaitme chercher, car il avait été engagé comme chauffeur de production. Nous avons parlé, un peu... Il n'était pas bavard !... Mais j'ai été frappé par son regard, très attentif. On sentait quelque chose d'intérieur, même si ses paroles étaient rares. On a fait un premier essai, qui atout de suite révélé sa présence physique à l'écran."
Lorsqu'ils se lancent dans le projet, le Français Richard Djoudi et l'Algérien Yacine Laloui, producteurs de La Trahison, nourrissent quelques craintes concernant les réactions des autorités algériennes. Mais deux jours après avoir reçu le scénario, le Ministère de la Culture (qui a consulté le Ministère des Anciens combattants) donne son feu vert pour le tournage. Les équipes franco-belge et algérienne s'installent alors à Bou Saada, ville située à environ 300 km au sud d'Alger, le tournage se déroulant dans le village El Hamel.
L'équipe a été très bien accueillie par les autorités du village d'El Hamel, comme en témoignent ces deux anecdotes rapportées par les producteurs. Tout d'abord, les villageoises ayant refusé de faire de la figuration, le maire décida de faire appel aux femme d'un village voisin. Celles-ci acceptèrent, ce qui provoqua la colère des premières... L'autre incident s'est produit durant le ramadan : l'équipe de tournage était gênée par la voix du muezzin, transmise par haut-parleur, qui appelait à la prière : "Je demande à l'imam de bien vouloir couper le haut-parleur extérieur. Je le sens très réservé, mais le chef spirituel de la communauté intervient et le haut-parleur est coupé..."
Le cinéaste revient sur un tournage qui lui laisse le souvenir d' "une belle expérience", malgré les difficultés : "Rien n'était simple, sur place. Tous les déplacements devaient être groupés, sécurisés et accompagnés, tout le temps. Mais il y a eu une implication énorme de l'équipe algérienne, que ce soit pour la construction des décors,la recherche des petits rôles, de la figuration, etc. Dans le village où nous tournions, avoir de la figuration ou des petits rôles féminins, pour tourner de nuit de surcroît, n'était pas toujours quelque chose d'évident. Mais j'ai pu tourner avec des gens extraordinaires. Il a fallu rechercher dans toute l'Algérie, et remettre en état, les derniers camions militaires restés sur place après le départ de l'armée française. Et dans le film, ils n'ont pas l'air de ce qu'ils étaient lorsqu'on les a récupérés : c'est-à-dire des tas de ferraille qui mettaient une heureà démarrer lorsque l'on devait tourner avec. Si le film est ce qu'il est, je le dois en grande partie à des gens là-bas qui sont devenus pour moi plus que des amis."
L'Algérie était déjà présente dans les deux précedents films de Philippe Faucon, à travers des héros issus de l'immigration : dans Les Etrangers, tourné pour Arte en 1999, il est question d'un jeune garçon d'origine algérienne, rejeté par sa famille parce qu'il est homosexuel, et qui décide de s'engager comme Casque bleu en Bosnie. En 2000, le cinéaste faisait dans Samia le portrait d'une adolescente d'origine algérienne et de son quotidien dans la banlieue marseillaise, entre désir de liberté et poids des traditions familiales.
Très tôt, dans les films français, des allusions sont faites à la guerre d'Algérie. Le héros d'Adieu Philippine de Rozier (1963) se prépare à faire son service, mais les "événements" séparent aussi les amants des Parapluies de Cherbourg de Demy (1964). Godard traite le sujet de façon frontale dans Le Petit Soldat, un film qui, pour cause de censure, ne sortira qu'en 1963, soit trois ans après son tournage. Dans les années 60 toujours, Alain Cavalier signe deux films politiques, Le Combat dans l'ile et L'Insoumis. En 1966 sort sans doute l'un des plus célèbres film consacré au sujet : La Bataille d'Alger de Gillo Pontecorvo. Malgré un Lion d'Or à Venise, un Prix de la critique à Cannes et 3 citations à L'Oscar, le film est interdit en France. Il ne sortira qu'en 1971 mais devant des menaces de représailles, il est rapidement retiré des écrans. Citons ensuite Avoir 20 ans dans les Aurès de René Vautier (1971), Elise ou la Vraie Vie de Michel Drach (1970) et R.A.S. de Yves Boisset (1973). Après ces oeuvres de dénonciation, les cinéastes peuvent évoquer le sujet de manière plus apaisée (Outremer de Brigitte Roüan en 1990, Les Roseaux sauvages d'André Techiné en 1994), même si Nico Papatakis signe en 1991 le très sombre Les Equilibristes. En 1999, pour Vivre au paradis, Bourlem Guerdjou, un film sur la vie des immigrés algériens à Nanterre dans les années 60, la manifestation du 17 octobre 1961 est évoquée à travers une reconstitution. Ce rassemblement (et la répression qui a suivi) sont au coeur de Nuit noire 17 octobre 1961, un film sorti en salles quelques semaines avant La Trahison.
Au départ, le réalisateur avait pensé intituler son film Le Choix.