L'idée du film est née de la volonté de John Duigan de porter à l'écran une époque qui lui est chère. "L'entre-deux-guerres est une période que j'ai intensément étudiée à l'université et pour laquelle je me suis toujours passionné" explique le réalisateur. Il ajoute: "L'extraordinaire bouillonnement des années 20 et 30 est une réponse au carnage de la première guerre mondiale. Cela était particulièrement vrai à Paris, où une scène artistique vibrante et féconde s'est considérablement développée à ce moment-là et où, psychologiquement, les gens ont préféré fermer les yeux sur l'éventualité d'une autre guerre".
Pour John Duigan, Nous étions libres n'est pas seulement une histoire de passion et de guerre, le film aborde également la question du destin et de la liberté d'action. "Le personnage de Gilda dépeint bien le dilemme" explique-t-il; "elle cherche à tout prix à contrôler sa vie, mais elle croit au fond d'elle que tout est pré-déterminé et que c'est son destin de mourir jeune (...). C'est pour cela qu'elle profite autant de la vie dans l'instant présent et ne ressent aucune obligation envers le cours du monde. Mais quand Guy et Mia partent en Espagne, la vie de Gilda est malgré tout bouleversée par les événements politiques , même si elle cherche à l'ignorer. Finalement, elle se rebelle contre cette idée et prend son destin en main, au péril de sa vie. La question reste de savoir si elle a ainsi déterminé ou si elle était depuis le début destinée à faire ce choix".
Le réalisateur, avec le chef décorateur Jonathan Lee et le costumier Mario Davignon, ont travaillé à partir de photographies, de tableaux, et de bandes d'actualités cinématographiques, afin de saisir dans les moindres détails l'époque de l'entre-deux-guerres. John Duigan précise: "Nous nous sommes aussi inspirés des peintres et des couturiers, avec des dessins de Chanel et de Schiaparelli qui définissent particulièrement bien la période".
Ce film évoque la période de l'entre-deux-guerres, les années 30, la Seconde Guerre mondiale et notamment l'occupation de Paris par les Nazis ou encore la guerre civile en Espagne. De nombreuses scènes ont été tournées en Angleterre (Londres, Cambridge) et à Paris. Le reste du tournage s'est effectué au Canada et tout particulièrement à Montréal.
C'est Charlize Theron -qui sortait du rôle qui lui a valu l'Oscar de la Meilleure actrice dans Monster- qu'a choisi John Duigan pour incarner la franco-américaine Gilda. "Charlize est une virtuose" raconte la réalisateur. "En tant qu'actrice, elle est à la fois très appliquée et très instinctive. Elle peut conserver la même émotion prise après prise. Le personnage de Gilda est brillant et spontané, mais elle a toujours ce sentiment amer que sa liberté est illusoire et Charlize réussit à faire passer cela brillament".
Le producteur britannique du film, Bertil Ohlsson, a été le producteur exécutif du multi-oscarisé Amadeus, en 1984. Il a également produit L' Insoutenable Légèreté de l'être, tiré du roman réputé inadaptable de Milan Kundera. On lui doit également la production de Gilbert Grape, dans lequel Johnny Depp et Leonardo DiCaprio se donnent la réplique.
L'acteur Allemand Thomas Kretschmann interprète le rôle d'un officier Nazi dans le film. Il avait déjà joué un tel rôle dans l'oscarisé Le Pianiste de Roman Polanski. Plus récemment, il a joué dans le film fantastique d'Enki Bilal: Immortel (ad vitam).
Charlize Theron a rencontré son compagnon Stuart Townsend sur le tournage de Mauvais piège. C'est la deuxième fois que le couple se retrouve à l'écran. Penélope Cruz complète ici le casting de ce triangle amoureux.
A l'origine, Natalie Portman et l'acteur sud-africain Jay Rodan devaient faire partie de Nous étions libres. Mais ils ont finalement été remplacés par Charlize Theron et Stuart Townsend.