Le cinéaste Ismael Ferroukhi a monté le projet du film après avoir découvert un article dans le Nouvel Observateur. Il y était expliqué que, durant la Seconde Guerre mondiale, la Mosquée de Paris servait d'abri pour de nombreux résistants et Juifs.
Ismael Ferroukhi et son co-scénariste Alain-Michel Blanc ont lu énormément de livres traitant de la condition des maghrébins dans le Paris du Régime de Vichy, plus généralement centrés sur la Résistance, la collaboration, le colonialisme et la situation de l'Afrique du Nord.
Deux historiens ont aidé Ismael Ferroukhi dans le cadre de ses travaux d'investigation : Benjamin Stora, expert du Maghreb, et Pascal Le Pautremat, théoricien sur l'Islam en France. Ferroukhi souhaitait pouvoir puiser dans des archives historiques si besoin est. L'objectif affiché du cinéaste étant de "Pouvoir me libérer ensuite de la matière véridique et investir la fiction."
Peu avant la Seconde Guerre mondiale, un nombre important de maghrébins sont venus travailler en France dans des usines. Ils se sont organisés en communauté et ont ouvert des cabarets, ainsi qu'un hôpital musulman et un cimetière. La plupart d'entre eux étaient analphabètes au moment d'arriver en France. Ces maghrébins se sont syndiqués et ont ainsi pu apprendre à lire et à écrire pour mieux défendre leurs droits fondamentaux. Un militantisme est ainsi né dans cette communauté. De ce fait, beaucoup se sont engagés dans des actions politiques pour combattre l'occupant allemand. Ismael Ferroukhi résume ainsi l'étrange paradoxe dans lequel ils se positionnaient : "Ils venaient d’un pays colonisé pour se retrouver dans un pays occupé."
En 1939, la France comprenait 100 000 maghrébins sur son territoire, dont 80% de Kabyles. Ces immigrés sont arrivés dans le pays depuis 1919 et se sont installés pour la plupart en Ile-de-France, aux alentours de Marseille, dans la vallée lyonnaise mais aussi dans le Nord-Pas-de-Calais et dans l'est du pays. Ils ont débarqué dans le contexte de l'implantation industrielle de la France de cette époque. Bien que ces individus soient issus de territoires sous administration française, comme l'Algérie, ils sont considérés par le reste de la population comme non-français. Pourtant, ils n'étaient pas recensés démographiquement comme étrangers à part entière ou sujets coloniaux. D'où un véritable flou sur leur identité nationale. On les appelait "les hommes invisibles" du fait qu'ils n'avaient aucune existence juridique ou culturelle et qu'ils étaient placés au dernier maillon de l'échelle sociale.
Avant la guerre, les Maghrébins de France se sont regroupés dans le cadre d'actions politiques de type nationaliste, par le biais d'organisations comme Étoile nord-africaine ou Parti du Peuple Algérien. Cela leur a permis d'obtenir une certaine visibilité. Lorsque la guerre éclata, la majorité de ces individus sont restés en France, et d'autres ont tenté de rejoindre le Maghreb. Ceux qui ont choisi de ne pas partir poursuivaient leur activité professionnelle. Ils participaient également à la construction du mur de l'Atlantique suite à une affectation ordonnée par le service de travail allemand durant l'Occupation.
Durant la Résistance, des travailleurs maghrébins, surtout algériens, se sont engagés dans des réseaux de luttes. Mais ces "hommes invisibles", considérés comme à part, ne pouvaient que difficilement s'inclure dans un système donné. Il faut savoir aussi qu'une minorité d'immigrés du Maghreb se sont laissés convaincre par le régime allemand et ont cru en leur promesse de libérer définitivement l'Algérie.
Durant ses recherches pour préparer son film, Ismael Ferroukhi a découvert l'existence de Si Kaddour Ben Ghabrit, le fondateur de la Mosquée de Paris, qui aura dirigé ce lieu religieux durant la période d'Occupation. Il s'agit, selon les dires de Ferroukhi, d'un homme aux multiples facettes, qui aimait fréquenter les milieux parisiens et qui vouait une véritable passion pour les arts. Durant la Seconde Guerre mondiale, Ben Ghabrit a sauvé sa grand-mère d'origine juive en empêchant son arrestation et en l'évacuant vers le Maroc.
Tout comme l'ensemble des institutions françaises d'alors, la Mosquée de Paris a collaboré avec le Régime de Vichy et les autorités nazies durant la Seconde Guerre mondiale. Pourtant, certains membres rattachés à la Mosquée ont refusé de se prêter à cette politique. De plus, la Mosquée a délivré des attestations d'appartenance à l'Islam pour protéger certains Juifs séfarades, ces derniers parlant couramment l'arabe.
Pour le personnage de Younès, joué par Tahar Rahim, Ismael Ferroukhi a tenu à ce qu'il évolue et change d'opinion tout au long du film. Si, au début de Les Hommes libres, il se présente comme quelqu'un de neutre, dont le seul souci est d'aider sa famille, le contexte de la guerre va le transformer petit à petit, sans que l'on sache réellement vers quelle voie il se dirige. Ferroukhi affirme que "le personnage ne pouvait pas évoluer trop vite et il fallait montrer qu’il traverse inévitablement des phases de doute, de tentations, de revirements, jusqu’au moment où il trouve son chemin et adopte une position ferme."
Bien qu'il ne soit pas d'origine maghrébine, Michael Lonsdale a été choisi pour incarner Si Kaddour Ben Gahbrit à cause de la puissance spirituelle qui se dégage de son jeu d'acteur. Hasard ou coïncidence, sa tante était une très bonne amie du véritable Gahbrit !
Dans Les Hommes libres, le personnage de Salim Hallali incarne une passerelle entre les communautés musulmane et juive. Il porte en lui cette hybridation culturelle et l'a fait véhiculer dans sa musique arabo-andalouse. Son succès au début des années 1940 dans les cabarets musulmans de Paris lui a assuré une protection contre la Gestapo.
La séquence du cimetière dans Les Hommes libres s'inspire d'éléments authentiques. Ben Ghabrit a fait falsifier un nom inscrit sur une pierre tombale afin de sauver un ami d'une déportation assurée.
L'accès à la mosquée de Paris a été refusé à l'équipe de tournage. Il a fallu qu'Ismael Ferroukhi aille effectuer des repérages au Maroc afin de trouver un décor de mosquée semblable à celui de la capitale française. Après avoir pensé tourner à Fès, le cinéaste a jeté son dévolu sur un ancien palais de Rabat, dans une région où la lumière n'est pas trop dissemblable à celle sur Paris.
Le chef opérateur Jérôme Alméras a opté pour un chevauchement entre des éléments chromatiques d'une certaine froideur pour refléter le Paris de l'Occupation, et des teintes plus solaires pour raviver l'ambiance des cabarets et des hôtels musulmans.
Bien qu'il n'y ait pas réfléchi de manière consciente, Ismael Ferroukhi admet que Les Hommes libres rappelle à de nombreux égards L' Armée des Ombres de Jean-Pierre Melville : "Je me suis rendu à l'évidence. Le film de Melville a influencé le mien, notamment dans les choix de décors et dans la manière dont les personnages se fondent dans les rues de Paris."
Pour les séquences musicales, une autre voix a été utilisée pour le personnage de Salim Hallali, celle de Pinhas Cohen, un chanteur marocain très populaire dans son pays. La particularité de son interprétation vocale tient au fait qu'il chante en arabe avec des "inflexions judaïsantes". La musique dans Les Hommes libres incarne, selon Ismael Ferroukhi, "un rapprochement immédiat entre les trois principales religions monothéistes (ndlr : christianisme, judaïsme et islam)."
L'élaboration de la musique du film a été confiée à Armand Amar. Ce dernier a opté pour une bande originale à base de trompette, un instrument qui, selon lui, permettait de refléter les états d'âme du personnage principal, Younes. Il a donc fait appel à un trompettiste, Ibrahim Maalouf, pour interpréter les partitions.
Les Hommes libres a été programmé dans le cadre d'une séance spéciale au Festival de Cannes 2011.