モーテルの一室で電話をしているレナード。相手はギャメル刑事ことテディだった。テディから、レナードの妻を殺した犯人ジョンGことジミーを見つけた、おびき出すから復讐を果たせと言われた。
レナードはテディから告げられた廃屋で待ち伏せし、やってきたジミーを絞殺した。そこにテディがやってきた。テディはレナードに、「ジミーは本当の犯人ではない、本当の犯人は以前俺が見つけ、すでにお前に復讐させた。しかしお前はそのことすら忘れてしまい、またすぐに犯人探しを始めた。俺はそんなお前を利用して、事件とは全く無関係のジミーを殺害させた。ジミーの車からヤクの取引のための金を奪うためにな」と打ち明けた。
レナードは復讐を果たしたことすら忘れてしまったことを受け入れられず、テディが自分に嘘をついて騙そうとしているのだと言い聞かせ、次の復讐相手はテディにすることを決心した。そして未来の自分に向けて、テディの写真に「やつを信じるな」と書き込み、テディの自動車のナンバーのタトゥを刻み込むことにした。
レナードは、ジミーのスーツと車を奪い、現場を去った。
レナードが、タトゥショップでテディの車のナンバーのタトゥを入れていると、テディが現れ、追われているから服も車も取り替えてさっさと逃げろと急かした。
テディの写真には「やつを信じるな」と書き込みがあった。さらにポケットの中には「後で来て。ナタリー」と書かれたコースターも入っていた。レナードは裏口から脱出してコースターの裏に書かれていたバーへ向かった。
バーのカウンターにいた女がナタリーだった。ナタリーはレナードと面識はなかったが、ジミーから聞いたことはある様子だった。なぜ来たのか尋ねられたレナードは、「記憶がないからわからないが、自分のスーツのポケットにこのコースターが入っていたからだ」とナタリーに差し出した。ナタリーは最初のうちは半信半疑だったが、どうやらレナードが記憶をすぐに失うというのは本当のことだと確信した。
ナタリーは自分の家にレナードを招いた。そして彼女は「しばらくこの部屋にいても構わない」とレナードに言い、仕事に出かけた。
やがて帰ってきたナタリーは、ドッドという男がここにくると騒ぎ始めた。ドッドは、ジミーがヤクを買うために大金を持ったまま消えたから、はめられたと思っている、そしてジミーの相棒である自分も共謀していると疑われている、このままでは危ないからドッドを殺してほしいとレナードに懇願した。
レナードが断ると、ナタリーは突然レナードに罵詈雑言を浴びせ始めた。激昂したレナードはナタリーを殴った。殴られたナタリーは「またね」と言って家を出ていった。
ナタリーはそのまま家の外の車の中で10分ほど時間を潰してから家に戻ってきた。その頃にはレナードにはもう直前の記憶はなかった。顔の傷を見て心配するレナードに、ナタリーは「ドッドに殴られた、明日までにヤクを持ってこないと殺すと脅された」と縋るように訴えた。
レナードは、自分がドッドのところへ行って話をつけると言い、ドッドの居場所の書いたメモを受け取ってナタリーの家を出た。
車に乗り込むと助手席にテディがいた。テディはレナードに「ナタリーを信用するな、彼女はドッドの始末をレナードにやらせるつもりだ」と警告した。そして、ナタリーとはもう会わずにモーテルへ行くよう促した。レナードがテディの写真の裏を見ると「やつを信じるな」と書き込まれていた。
レナードは、テディに紹介されたモーテルにチェックインした。
そして、デートクラブに電話して娼婦を呼び出した。やってきた娼婦に、妻の思い出の品を部屋に置くよう、そして夜中にバスルームのドアを音を立てて閉めるよう求めた。妻が殺された夜を再現して、記憶を取り戻そうとしたのだ。
娼婦はレナードの指示に従うが、記憶は戻らなかった。失望したレナードは娼婦を帰した。
レナードはそのまま妻の思い出の品を入れた紙袋を抱えて、空き地でそれらを燃やし始めた。レナードは、いくら燃やしても妻のことを忘れられない、と独り物思いに耽った。
朝になってモーテルに帰る途中、突然後ろから煽られ銃撃された。レナードは車から脱出し走って逃げた。
逃げ回って自分の車に戻ったレナードは、運転しながらナタリーから受け取ったメモを見た。そこには、”ドッド 白人 ５番通りのクレスト・イン”と書かれていた。
先回りしてドッドの部屋に入ったレナードは、近くにあったスコッチの瓶を武器代わりに握りしめバスルームで待ち伏せした。
やがて戻ってきたドッドをレナードは殴り倒して拘束した。写真の間に挟まっていた「ドッド テディに連絡を ナタリーのために消せ」というメモに従ってテディに電話すると、そのまま疲れて眠ってしまった。
しばらくして目覚めると、テディがやってきた。
レナードが拘束したドッドを見せると、テディは驚いた様子だった。
拘束時に撮影したドッドの写真を見ると、「消せ。ナタリーに聞け」と書き込まれていた。
結局、町外れまでドッドを連れていき、そのまま町から追放することにした。
レナードは、事情を確認するためナタリーのところへ行くことにした。
レナードからドッドの写真を見せられて、ナタリーはドッドの件が片付いたことを知った。
ナタリーは、妻を失い辛い思いをしていると打ち明けるレナードに、自分も大切なジミーを失い同じように辛い思いをしたと同情する素振りを見せ、彼の復讐に協力すると申し出た。
夜、レナードはナタリーの写真に「彼女も恋人を亡くし憐れみで協力を」と書き込んだ。
翌朝、ナタリーがレナードの入れ墨にある車のナンバーの所有者を調べてみると請け負ってくれた。二人は後で会うことにし、レナードはナタリーの家を出た。
車を発進させようとするとテディが姿を現した。テディは、ジョンGを見つけ出すため協力すると約束してくれた。
モーテルの鍵がないので、フロント係のところへ行った。フロント係は少し慌てた様子で、「レナードの記憶がなくなることを良いことに、モーテルのオーナーの指示で彼に二部屋貸していたんだ」と決まり悪そうに告白した。フロント係はレナードに必ず領収書をもらえと忠告された。
レナードがそのことをメモに取ろうとボケットを探ると、ナタリーとの待ち合わせに関するメモが見つかった。
レナードは、メモに従いナタリーとの待ち合わせ場所に行った。ナタリーから、車検局の知人からの情報で車の持ち主がわかったと封筒を渡された。
どうせ復讐しても忘れるのではと揶揄されるが、レナードは写真を撮るから忘れないと反論した。
ナタリーは復讐するのに都合がいい、郊外の廃屋の住所も入れておいたとレナードに言い残した。
モーテルに戻って封筒を開けると、中には免許証のコピーが入っていた。その免許証にあるのはテディの顔写真だったが、名前はジョン・ギャメル（レナードは忘れているが、テディの本名）となっていた。
腕のタトゥには事実１：男 事実２：白人 事実３：ファーストネーム、ジョン 事実４：ラストネームはG？？？ 事実５：ドラッグディーラー 事実６：免許証番号SG137IUと刻まれていた。それらはテディという名の男の免許証のコピーと一全て致していた。
レナードはテディの写真に、「奴を殺せ」と書き込んだ。
フロント係に、テディから電話が来たらつなぐよう頼んでいると、本人が現れた。
レナードはテディを乗せ、ナタリーのメモにあった廃屋に向かった。そこは、かつてレナードがジミーを殺害した場所だった。
レナードがテディの写真を見ると、”テディの嘘を信じるな、奴が犯人だ。奴を殺せ”と書き込まれていた。
レナードはテディに、一緒に地下室に行けば何があったか全て分かると説得されるが、自分のメモを信じ、テディを撃ち殺した。
