Le matin de la saint Valentin, Joël Barish, timide, dépressif et routinier, décide, sans raison particulière, de ne pas aller au travail et de prendre le train pour Montauk. Là-bas, il rencontre Clémentine Kruczynski, extravertie, excessive et délurée. Ils sont irrémédiablement attirés l'un vers l'autre et après une nuit sous les étoiles, sur un lac gelé, ils tombent amoureux. Clémentine s'arrête chez elle, le temps d'aller chercher sa brosse à dents pour aller dormir chez Joël. Un jeun garçon demande à Joël s'il peut l'aider
Tout à coup, Joël est en pleurs, dans sa voiture alors que lee générique défile. Joël est chez ses amis Franck et Carrie à qui il fait part de son désarroi et surtout de son incompréhension. Alors que plus tôt dans la journée, il s'est rendu au travail de Clémentine pour lui offrir un bijou de Saint-Valentin, il est resté choqué de voir qu'elle s'adressait à lui comme si elle ne le connaissait pas et qu'en plus elle avait un nouveau petit ami. C'est alors que Franck montre à Joël une étrange carte de la société Lacuna, qu'ils ont reçu, stipulant que Clémentine avait fait appel à cette clinique pour éradiquer tout souvenir de lui de sa mémoire. Effondré, Joël veut comprendre. Il rencontre le Dr Howard Mierzwiak, gérant de Lacuna et décide de faire de même avec ses souvenirs de Clémentine.
Il est donc plongé dans une sorte de coma durant lequel les souvenirs sont effacés au fur et à mesure que Joël se les remémore, du plus récent au plus ancien. Mais le conscient et l'inconscient se mélangent, tout comme le passé et le présent. Joël entend ce qui se passe autour de lui dans la réalité, revit ses souvenirs, ressent ses pensées et étrangement sa conscience influe sur sa mémoire. Il se souvient que trois employés de Lacuna, Mary la secrétaire, Stan et Patrick les "effaceurs" se sont introduits à son domicile pour le brancher au processus de destruction de souvenirs.
Tandis que Mary et Stan s'amusent et flirtent ensemble, Patrick, tombé amoureux de Clémentine lors de sa lobotomie, en a profité pour usurper l'identité de Joël dans le cœur de celle-ci et part la rejoindre. Joël entend impuissant les trois employés autour de lui et comprend comment Patrick a pris sa place, volé tous les objets, documents, photos. Joël revit en sens inverse sa relation, en commençant par la dernière dispute qui a amené Clémentine à choisir de faire effacer sa mémoire.
De son côté, Clémentine ressent un malaise dans sa relation avec Patrick, elle a des angoisses et comportements qu'elle ne s'explique pas, comme son besoin soudain d'aller à Montauk voir le lac gelé. Quant à Joël, si au début il remontait les souvenirs les plus récents, donc les moins agréables, plus l'expérience avance, plus il revit de beaux et doux souvenirs. Il comprend alors qu'il est toujours amoureux de Clémentine et veut annuler l'opération, mais personne ne l'entend. Grâce à sa volonté, il parvient à emmener le souvenir de Clémentine dans sa mémoire d'enfance, là où normalement elle n'existe pas.
Stan et Mary s'aperçoivent que Joël n'est plus en phase avec le processus, ils sont contraints d'appeler le Dr Mierzwiak en urgence. Celui-ci parvient à contrecarrer les tentatives de Joël de se cacher de la carte des souvenirs de son histoire avec Clémentine. Alors Clémentine s'efface de tous ses souvenirs, même les faux car Joël ne parvient plus à l'emmener avec lui dans sa mémoire, à la garder. Pendant ce temps là, Mary se pavane devant le Dr Mierzwiak et l'embrasse ce qui interrompt le travail momentanément. La femme du docteur débarque à l'improviste et Mary découvre alors qu'elle a déjà eu une relation avec celui-ci mais qu'elle n'en a plus de souvenirs puisqu'elle lui avait demandé de les effacer. Le Dr Mierzwiak retourne poursuivre le processus de Joël qui de son côté revit les derniers souvenirs qui lui restent.
Mary quant à elle retourne à la clinique et retrouve son dossier et les cassettes consignées de son propre processus d'amnésie sélective. Pendant ce temps-là, Joël revit, impuissant, le souvenir de sa rencontre avec Clémentine et la fin de ses souvenirs : leur première rencontre sur la plage. Tout deux savent maintenant qu'ils vont disparaitre de leur mémoire. Ils tentent de faire meeiux que cette première nuit où Joël avait fuit et de se dire un bel adieu. Dans un dernier baiser, Clémentine lui glisse alors à l'oreille : "rendez-vous à Montauk".
L'équipe de Lacuna libère l'appartement de Joël qui se réveille. C'est le jour de la saint Valentin. Joël décide, sans raison particulière, de ne pas aller au travail et de prendre le train pour Montauk. Mary quitte la clinique en volant les archives de Lacuna. Joël et Clementine, du retour du lac gelé, sont amoureux et Clémentine monte chez elle récupérer une brosse à dents. Elle écoute sur son répondeur un message de Patrick et trouve dans sa boîte aux lettres une lettre de Mary, accompagnée de son dossier et de la cassette enregistrée lors de son processus. Joël et Clémentine commencent à l'écouter sur l'auto-radio. Joël, ne supportant pas les critique de Clémentine qu'il entend, la fait descendre de voiture. Blessée, Clémentine le rejoint chez lui un peu plus tard, après s'être débarrassée de Patrick. Lorsqu'elle arrive à son appartement c'est la cassette de Joël qui est diffusée sur la chaîne hi-fi. Désorientés, blessés, ils se quittent avant de s'avouer que, même s'ils savent que leur relation peut être vouée à l'échec, il faut la recommencer, retenter leur chance.
La séquence pré-générique se situe après l'effacement de la mémoire de Joël et de Clementine. Il faudra dérouler la presque totalité du film pour revenir à la fin de cette séquence (le matin de la brosse à dent) et poursuivre avec la conclusion heureuse.
Le film décrit, avec lyrisme et invention, l'ensemble des combats douloureux et acharnés des personnages pour réaliser et assumer leur amour alors qu'ils sont si différents et donc sujets aux ruptures.