Il s'agit du sixième projet commun de Tony Scott et du producteur Jerry Bruckheimer après Top Gun, Le Flic de Beverly Hills 2, Jours de tonnerre, USS Alabama et Ennemi d'Etat. Déja vu est aussi le troisième film de Tony Scott avec l'acteur Denzel Washington qui a déja joué dans USS Alabama et Man on Fire.
Lors de la lecture du scénario de Déjà vu, Jerry Bruckheimer, a été d'emblée séduit par le projet: " Le concept était original, le suspense réel, et l'histoire d'amour résolument différente de ce qu'on a déjà pu voir au cinéma. Quarante-huit heures après avoir reçu le scénario, nous l'achetions. ". Le scénariste Terry Rossio avait déjà collaboré avec Jerry Bruckheimer sur la trilogie de Pirates des Caraïbes. Bill Marsilli aussi scénariste de Déjà vu et Terry Rossio se sont rencontrés sur un forum internet où ils s'entretenaient avec des scénaristes débutants. Ils ont continué à s'échanger des concepts de scénarios par mail, puis ils ont ensuite développé le projet de Déjà vu.
La distribution de Déjà vu réunit des acteurs confirmés comme Jim Caviezel qui interpréte le rôle du suspect Carroll Oerstadt : " Je n'ai pas pu résister au mélange de coups de théâtre et de questions passionnantes sur la nature de la réalité ! C'est une histoire très complexe, mais qui mieux que Jerry Bruckheimer et Tony Scott pouvaient en faire une telle expérience de cinéma ? C'est un thriller à couper le souffle qui ouvre des perspectives fascinantes et fait intervenir le visible et l'invisible... ". Paula Patton fait aussi parti du casting, elle incarne le rôle de Claire Kuchever, une femme forte et courageuse. Ce film lui a aussi donné l'occasion de touner au côté de Denzel Washington , avec lequel elle a entretenu de bons rapports pendant le tournage : " Travailler avec Denzel est comme de jouer avec un musicien de jazz. Il suit le scénario mais est capable de partir dans d'autres directions. Il a une totale confiance en son instinct. Cela demande une vigilance constante de la part de ses partenaires, parce qu'on ne sait jamais où il va s'aventurer! ". Quant à Val Kilmer, il retrouve Tony Scott avec lequel il avait collaboré dans Top Gun.
Pour bien se préparer au rôle d'un agent de la Brigade ATF (Alcohol, Tobacco and Firearms), Denzel Washington a fréquenté Jerry Ruden, véritable agent de la Brigade pendant 20 ans. Il a notamment enquêté sur l'explosion de l'Alfred E.Murrah Building et sur l'affaire de la voiture piégée près du World Trade Center en 1993. Jerry Ruden a également travaillé avec le producteur et Jim Caviezel , pour dresser un portait réaliste d'un poseur de bombe. Son aide a permis de donner une certaine authenticité au scénario.
L'histoire d'amour racontée à l'envers dans le scénario de Déja vu a particulièrement plu à Denzel Washington: "Je n'étais pas seulements fasciné par le côté thriller de l'histoire, mais surtout par l'étrange relation qui se noue entre mon personnage et celui de Paula Patton: j'aime cette idée que c'est une histoire d'amour à l'envers où mon personnage rencontre une jeune femme morte avant même qu'il la connaisse et qui se voit offrir une chance de la voir en vie. Ca semble compliqué à première vue, mais avec Tony Scott et Jerry Bruckheimer impliqués dans le projet, je savais que ça allait donner quelque chose de grandiose".
Psychanalystes, médecins et scientifiques partagent leurs points de vue sur la théorie du déja- vu. Les neurologues pensent que l'impression de déjà-vu se produit lorsque le cerveau se " bloque " sur un un détail (une odeur, un son, une image) dont la familiarité engendre une confusion entre le passé, le présent pendant une fraction de seconde. Quant aux médecins, ils ont constaté que cette sensation de déjà-vu se manifeste lorsque le patient a subi des attaques cérébrales. Les psychanalystes sont pour l'hypothése que le déjà-vu est une forme " d'accomplissement des souhaits ", dans lequel des désirs psychologiques profonds remontent à la surface comme ils le font durant les rêves, mais à l'état de veille. Pour ceux qui croient à la réincarnation, les episodes de déjà-vu sont des preuves de la mémoire des vies antérieures. Pour développer l'intrigue du film, Tony Scott et Jerry Bruckheimer se sont surtout attachés à la théorie des scientifiques qui pensent que la sensation de déjà-vu pourrait être le résultat d'univers parallèles interférant accidentellement lorsque la trame de l'espace-temps est interrompue. Ils ont fait appel à des physiciens dont le Dr Brian Greene, qui leur ont expliqués des théories sur le voyage dans le temps et les univers parallèles. Tony Scott explique :"Je veux que les spectateurs quittent les salles en se disant que ce genre de voyage dans le temps est réellement possible. Si la technologie nécessaire n'existe pas encore, les scientifiques le rendront possible demain."
Le producteur Jerry Bruckheimer explique en ces termes le concept de Déjà vu: " Nous sentions l'immense potentiel dramatique que comportait le scénario de Déja vu avec tout ce qu'il apportait autour de l'histoire d'amour. L'idée de pouvoir ramener à la vie une personne qu'on aime est un magnifique concept. Le scénario est riche en rebondissements, divertissant, et plein de romance. De plus, en amenant Tony Scott sur le projet, nous étions sûr que ce film serait rempli de scènes d'actions exaltantes. (...) Nous avions tous les deux le même objectif pour ce film: vous emmener pendant deux heures pour que vous oubliez tout et que vous vous perdiez dans la magie du spectacle. Qaund les lumières de la salle s'éteignent, vous êtes immergé dans un autre monde, le monde de Déja vu.
Les effets visuels sont spectaculaires grâce aux procédés techniques utilisés dans le film. Ainsi Tony Scott, s'est servi de plusieurs caméras, dont la caméra haute définition Genesis qui permet des éclairage très faibles sans altérer la qualité de l'image. La caméra Tim Track de Digital Air permet de donner l'impression d'un mouvement figé dans le temps alors que la caméra Lidar permet de scanner les structures comme avec la maison de Claire. Le réalisateur explique : " Pour moi, ces caméras ont été autant d'outils pour l'enquête qu'est le film. Tous les styles d'images de DEJA VU s'unissent pour rendre plus convaincant encore le mélange d'histoire d'amour, d'enquête criminelle et de voyage dans le temps. ". Des techniques militaires ont été aussi employées dans le film , tels que l'infrarouge, l'imagerie thermique par heat impulse, ajoutent une dimension réaliste au film.
Sur le tournage, Tony Scott a mis les acteurs à rude épreuve. Ils ont chacun eu droit à des exercices périlleux. Ainsi Paula Patton a tourné une scène sous l'eau dans le Mississippi, les mains liées, et sans bouée de protection. Quant à Denzel Washington, pendant qu'il tournait sous le pont de Mississipi, il a du grimper par dessus des grilles pour se retrouver ensuite sur des planches étroites à 100 m de haut environ. Jim Caviezel a eu droit à un exercice différent. Protégé par une cage en acier, une voiture devait foncer sur lui , il raconte : " Ils m'ont mis dans une cage et ont lancé deux voitures sur moi ! Je n'arrêtais pas de penser que si la cage cédait, je n'aurais plus de jambes... "
A l'instar de Joel Silver pour Matrix reloaded, le producteur Jerry Bruckheimer est particulièrement fier de la scène de poursuite en voiture qui risque de révolutionner le genre selon lui: " La poursuite en voiture dans ce film est vraiment impressionnante. On n'a jamais rien vu de pareil!. C'est une course poursuite qui se déroule sur deux espaces temporels, et en plein trafic. A un moment, Denzel fait demi-tour et roule à contre-sens. En l'espace de 15 secondes, il y a cinq voitures qui explosent et qui se crashent. C'est vraiment étonnant !"
Une équipe spéciale a été assignée pour capturer les millions d'images qui défilent sur les 72 écrans de surveillance du Laboratoire. Au final, cette équipe aura filmé 500 heures de vidéo et d'images pour qu'elles n'apparaissent qu'un court instant sur chaque écran.
Tony Scott a failli ne pas réaliser le film. En effet, suite aux ravages de l'ouragan Katrina en octobre 2005, il était impossible de tourner en Nouvelle-Orléans, l'un des principaux décors du film. Déçu, Tony Scott a quitté le projet, entraînant avec lui le désistement de l'acteur prinicipal Denzel Washington. Mais finalement, le Bureau du Film et de la Télévison de Louisiane a convaincu les producteurs des bonnes conditions de tournage, voyant dans ce film l'occasion de ramener une belle image de la région. Une partie des employés de l'équipe du film ont d'ailleurs été engagés sur place, ce qui a aidé à relancer l'économie. Le tournage a donc commencé en janvier 2006 comme c'était prévu initialement. Déja vu est considéré comme la première fiction post-Katrina.
Denzel Washington a été extrêmement touché par cette région sinistrée de la Nouvelle Orléans qui essayait d'émerger des décombres causés par l'ouragan Katrina : " J'ai été vraiment ému par les gens que j'ai rencontré et qui se battaient pour reprendre leurs vies. Je prenais la voiture tous les jours et je circulais autour de la ville pour parcourir des kilomètres et des kilomètres de dévastation. Je n'oublierais jamais ce que j'ai pu voir".