Melinda et Melinda renferme deux films, une comédie et un drame, chacun étant imaginé par un scénariste différent. Un montage alterné permet au spectateur de suivre en parallèle l'évolution des deux intrigues. Melinda est le seul personnage commun aux deux histoires, et, par conséquent, Radha Mitchell est la seule comédienne qui passe d'un registre à l'autre. Ainsi, Chloë Sevigny, Chiwetel Ejiofor et Jonny Lee Miller apparaissent-ils uniquement dans la partie dramatique, tandis que Will Ferrell et Amanda Peet interprètent les protagonistes de la comédie. Radha Mitchell raconte : "Woody n'a jamais voulu de quelqconque explication psychologique. Dès le début du tournage, j'interprétais le matin une scène de "comédie" et l'après-midi une autre plus sombre. Sans commentaire ni précision du metteur en scène, je me suis sentie finalement plus libre, j'ai pu mettre en place ma propre vision des choses, et proposer des idées.". "On aurait dit que nous tournions dans deux films distincts !", précise Sevigny. "Parfois, on allait voir ceux qui jouaient dans l'autre histoire pour leur murmurer : "Et vous, qu'est-ce que vous fabriquez ?"" se souvient Ferrell.
Woody Allen parle de Melinda, le personnage principal de son film : "Des deux Melinda, aucune n'est la vraie ou la fausse. Elles sortent toutes deux de l'imagination de Sy et de Max, les deux auteurs qui discutent au restaurant. L'un rattache son histoire à la tragédie, l'autre l'oriente vers le rire. Parfois les deux versions se recoupent, parfois elles divergent (...) C'est par accident que j'ai fait des progrès dans l'écriture des personnages féminins. Au fil des années, film après film, les rôles principaux allaient de plus en plus aux femmes. Alors j'ai dû travailler. Je suis plus à l'aise, maintenant. Quand j'écris un personage masculin, j'écris d'habitude pour moi, ou pour une autre version de moi-même."
Pour tenir le(s) rôle(s) de Melinda, Woody Allen a choisi la comédienne australienne Radha Mitchell, après l'avoir remarquée dans Four reasons, un court-métrage en noir et blanc qu'elle a écrit, réalisé et interprété en 2002 : "Je revenais d'un long voyage et quand le téléphone a sonné", raconte l'actrice, vue notamment dans le film indépendant High Art et le blockbuster Phone game. "J'ai pensé que c'était ma mère qui voulait prendre de mes nouvelles. J'ai décroché, c'était Woody Allen en personne. Il me proposait un rôle. Il m'envoyait le scénario le jour même."
S'agissant de l'image, le chef-opérateur Vilmos Zsigmond précise : "Woody s'est opposé à ce que l'on différencie clairement à l'image le traitement de la comédie et du drame. Je n'ai fait que prendre des angles de plan moins élevés et ajouter un peu d'ombre pour les scènes plus "tragiques". Et il y a plus de mouvements dans les scènes légères. La caméra est à hauteur d'homme." En ce qui concerne la musique, le réalisateur (et clarinettiste...) explique : "J'ai cherché à construire une ambiance distincte entre les deux tons de récit, mais sans insister. Stravinsky pour les instants sombres et Duke Ellington pour les scènes plus légères. Et puis au bout d'un moment j'ai tout mélangé."
Melinda et Melinda repose sur l'idée qu'une même histoire peut donner lieu à une comédie ou à un drame. Woody Allen s'est essayé à ces deux registres tout au long de sa carrière. Ses premiers films sont particulièrement burlesques, notamment Bananas (1971) et Tout ce que vous avez toujours voulu savoir sur le sexe... sans jamais oser le demander (1972). Quelques années plus tard, le cinéaste a tourné des films beaucoup plus sombres, comme Intérieurs (1978) ou Une autre femme (1988). Fantaisie et mélancolie se mêlent dans de nombreuses oeuvres du réalisateur, de Annie Hall (1978) à Maris et femmes (1992) en passant par Stardust Memories.
Winona Ryder et Robert Downey Jr. étaient pressentis pour jouer dans Melinda et Melinda, mais le montant des primes d'assurances étant trop élevé en raison des démêlés judiciaires de ces comédiens, Woody Allen a dû renoncer à cette première idée de casting. Le cinéaste a ensuite pensé confie ce rôle à Jason Biggs, héros de son précédent film, Anything else, la vie et tout le reste.
Nouvelle venue dans l'univers de Woody Allen, l'icône new-yorkaise Chloë Sevigny est une des héroïnes de la partie "dramatique" de Melinda et Melinda. Le réalisateur, qui l'admire depuis longtemps, avait songé à lui confier des rôles dans ses deux précédents films. "Je crois que depuis Les Derniers jours du disco, il savait que je saurais jouer ce genre de fille, être à l'aise dans ce milieu social-là, où tout semble facile mais où tout peut s'écrouler... Je connaissais déjà Jonny Lee Miller [qui incarne son mari dans le film], nous nous étions rencontrés à Cannes au moment de Trainspotting. Cela m'a facilité les choses."
Personnage central dans la partie "comique" de Melinda et Melinda, Will Ferrell est connu pour ses prestations dans des films délirants tels que Austin Powers ou Zoolander. "Disons que mes films ont tendance à être un peu plus sophistiqués que les rôles qui l'ont rendu célèbre. Mais il est épatant", s'amuse le cinéaste. Ferrell estime que Hobie est le personnage "le plus realiste" qu'il ait eu à interpréter. "J'ai beaucoup apprécié de pouvoir interpréter un dialogue tout simple, sans avoir recours à des costumes grotesques, sans avoir la pression de devoir être drôle à tout prix. L'humour est déjà dans le contexte du récit."
Fille d'une psychanalyste, Amanda Peet a grandi à Manhattan. "Woody Allen est mon héros", dit la comédienne, qui confie par ailleurs avoir demandé des conseils à l'actrice-fétiche du réalisateur, Diane Keaton, qui fut sa partenaire dans Tout peut arriver de Nancy Meyers (tourné en 2003).
L'essentiel de la distribution de Melinda et Melinda est constitué de comédiens qui n'avaient encore jamais tourné avec Woody Allen. En revanche, les deux scénaristes, dont les discussions ouvrent et closent le film, sont interprétés par des acteurs familiers de l'univers du réalisateur new-yorkais : Larry Pine (l'auteur de tragédies) est apparu dans Celebrity et Escrocs mais pas trop. Quant à l'auteur de comédies, il a les traits de Wallace Shawn, qui est lui-même auteur dramatique, et a tourné dans l'un des plus fameux films d'Allen, Manhattan, en 1979 "(...) je n'avais pas l'ambition de devenir comédien. Je n'en avais même pas l'envie (...) Grâce à Woody Allen, je suis devenu un peu acteur. Puis d'autres réalisateurs m'ont vu dans ses films (Radio Days, Ombres et brouillard et Le Sortilège du scorpion de Jade) et m'ont demandé (...) Aujourd'hui, vu le genre de théâtre que j'ai toujours écrit, je ne vis pas de ma plume. C'est en jouant que je gagne ma vie. C'est donc, vous le comprenez, un immense cadeau que m'a fait monsieur Woody Allen. Grâce à lui, je suis à peu près libre d'écrire ce que je veux."
Woody Allen a fait appel pour la première fois au chef-opérateur d'origine hongroise Vilmos Zsigmond. On lui doit l'image de classiques du cinéma américain tels que L' Epouvantail de Jerry Schatzberg, Délivrance de Boorman, La Porte du paradis de Michael Cimino, ou encore Rencontres du 3e type de Steven Spielberg, qui lui valut l'Oscar de la meilleure photographie en 1978.
Plutôt que Venise, Cannes ou Berlin, Woody Allen a choisi le Festival de San Sebastian pour présenter Melinda et Melinda à un public international, en septembre 2004.