"Au départ, j'avais lu un scénario de Philippe Blasband qui traitait de la relation entre une femme et une prostituée. Il s'agisssait d'une histoire de vengeance, de piéger un mari qui n'apparaissait qu'à la fin. Ce qui m'a intéressé, c'était de partir d'une femme mariée qui engageait les services d'une professionnelle, et qui vivait, sans l'avoir décidé vraiment, un rapport au sexe par procuration", explique la cinéaste.
Avec Nathalie..., Anne Fontaine met en scène un trio amoureux, situation qu'elle a déjà explorée dans ses précédents films. Dans Les Histoires d'amour finissent mal... en general, son premier long-métrage, prix Jean Vigo en 1992, une femme est amoureuse de deux hommes. Dans Nettoyage à sec, un couple tranquille formé par Miou-Miou et Charles Berling est troublé par l'arrivée d'un jeune homme. Cette fois, c'est une femme, entraîneuse dans un bar, qui fascine le couple interprété par Gérard Depardieu et Fanny Ardant.
Initialement, c'est Vanessa Paradis qui devait jouer le rôle de Nathalie..., l'héroïne du film d'Anne Fontaine. Mais l'actrice et chanteuse a dû renoncer au film pour cause de grossesse. Après la défection de Paradis, la réalisatrice s'est tournée vers l'héroïne de L'Enfer, Emmanuelle Béart.
Fanny Ardant, qui interprète un des rôles principaux de Nathalie..., est déjà apparue dans un film précédent d'Anne Fontaine. La comédienne joue son propre rôle dans une scène d'Augustin roi du kung-fu.
Emmanuelle Béart confie que Marlène a été pour elle un rôle d'autant plus délicat qu'elle avait enchaîné les tournages de deux films importants, Les Egarés et Histoire de Marie et Julien, juste avant celui de Nathalie... La complicité de Fanny Ardant lui a été précieuse, ainsi qu'elle le raconte : "Je venais de tourner successivement le film de Téchiné et de Rivette. j'étais exsangue, cet état pouvait servir le personnage de Marlène, mais il fallait la patience de Fanny, son regard, sa bienveillance et sa gaieté (...) Sans Fanny, je ne suis pas sûre que j'aurais tenu le coup. Un peu comme Catherine et Marlène vont toutes deux chercher chez l'autre ce qu'elles n'ont pas. Etrangement, j'ai trouvé une forme de sensualité pour mon personnage en regardant Fanny, son charme un peu lascif, sa voix, sa gestuelle."
Pour le rôle d'entraîneuse que lui a proposé la cinéaste, Emmanuelle Béart a exploré un univers qu'elle a déjà approché : "La prostitution ne m'était pas étrangère. Récemment, lors d'un voyage en Thaïlande pour enquêter sur la prostitution enfantine, j'ai vu ce qui se passait autour du tourisme sexuel. Il m'est arrivé aussi, à Paris, de prendre le bus des Femmes qui vient en aide aux prostituées. Dans le cadre du rôle, nous sommes allées avec Anne Fontaine dans ce genre de clubs où travaille Marlène (...) Il ne s'agissait pas d'en prendre une pour modèle, mais d'essayer de voir quelle est la part de jeu dans l'exercice de leur profession, et quelle est leur vie de femme avant, pendant, et après" raconte l'actrice, qui avait déjà joué en 1991 le rôle d'une prostituée dans J'embrasse pas d' André Techiné.
Dans ce film sur le désir, l'érotisme passe beaucoup par le langage. Anne Fontaine justifie ce choix : "Je ne pourrais imaginer faire un film où la représentation du sexe soit littérale, le sexe est tellement sur-représenté, on en connaît toutes les figures. Ce parti-pris de laisser flotter l'imaginaire est à la fois plus pervers, et plus excitant. Le visage de Fanny, écoutant ces gestes vécus, transférés par des mots...c'est évocateur ! Le langage a une puissance érotique très forte, la voix aussi. J'ai d'ailleurs choisi ces deux actrices pour leur voix."
Plus de vingt ans après avoir été les amants passionnés de La Femme d'à côté, et dix ans après avoir formé un couple singulier dans Le Colonel Chabert, Gérard Depardieu et Fanny Ardant sont de nouveau mari et femme dans Nathalie X. L'acteur parle ainsi de sa partenaire : "Fanny est un amour de femme. J'ai une amitié amoureuse avec Fanny. On a quand même passé pas mal d'heures de vol ensemble. Et puis Fanny n'est pas une actrice. Fanny est une femme. Une femme généreuse, belle."
Avant de partager l'affiche de Nathalie..., Emmanuelle Béart et Fanny Ardant étaient deux des 8 femmes dans le film de François Ozon. Par ailleurs, Emmanuelle Béart - Manon des Sources était la fille de Gérard Depardieu - Jean de Florette dans le diptyque réalisé par Claude Berri. Mais Manon n'apparaît que dans le deuxième volet, après la mort de son père Jean à la fin du premier...
Pour ces film dans lequel un soin particulier a été apporté au choix des tenues de Nathalie/Marlène, l'entraîneuse, la cinéaste a fait appel à la costumière Pascaline Chavanne, dont le travail sur le film 8 femmes a été particulièrement remarqué.
Le film a plusieurs fois changé de titre : il s'est d'abord appelé Nathalie Ribout, puis Nathalie X. Le mystère s'épaissit un peu plus avec Nathalie..., le titre finalement choisi par la réalisatrice.
Jacques Fieschi connaît bien Emmanuelle Béart pour laquelle il a coécrit plusieurs scénarios de films avant Nathalie...: Un coeur en hiver et Nelly et Monsieur Arnaud de Claude Sautet, ainsi que Les Destinees sentimentales d'Olivier Assayas. C'est par ailleurs la troisième collaboration de Fieschi avec la réalisatrice Anne Fontaine.