Le choix d'une femme fatale
Brian De Palma voulait une inconnue pour incarner l'héroïne de Femme Fatale afin de créer la surprise. Au cours d'une rencontre entre le producteur Tarak Ben Ammar et John McTiernan à Los Angeles, ce dernier lui parla de Rebecca Romijn-Stamos qu'il venait de diriger dans Rollerball (2001). Dès le week-end suivant Brian de Palma lui fit passer des essais à Paris qui se révélèrent très concluants.
Un directeur photo français
Brian De Palma a choisi Thierry Arbogast au vu de son travail avec Luc Besson et sur le film L' Appartement de Gilles Mimouni (1996).
Brian de Palma à Paris
Brian De Palma qui apprécie beaucoup la France voulait absolument y tourner un film. Il a emménagé à Paris et fait lui-même les repérages de Femme Fatale pendant plusieurs mois, en parcourant la ville à scooter afin de découvrir des endroits où les cinéastes américains n'avaient jamais tourné.