映画では何か事件があると「○か月前」などと遡って種明かしがあり、こんな裏があったのかと分かって驚く。これが何度となく続く。多少分かりにくいので、時系列に沿って並べた。
モスクワ、1985年。CIA女性工作員が「身元がばれた。すぐ大使館に行け」と電話を受ける。電話した男性、買い物中の女性、研究員、通訳、米国人女性旅行客を装ったCIA工作員も次々にKGBに連行される。大使館前に着いた女性工作員が開門を待っていると、車が突っ込んでくる。CIAに9個の小包が届き、レナード・ミラーが開けると女性工作員の首が入っていて驚く。
1987年。アナはモスクワでペーチャと暮らしていた。ホームレスだったアンは彼に拾われ、暴力や性的虐待に苦しめられていた。アナはこの生活から抜け出そうとネットから海軍に応募する。
アンが買い物帰りに歩いていると、盗難車に乗ったペーチャとその友達に車に乗せられる。誘拐した米国人のカードで、ATMから金を盗む。パトカーが来て、警官を撃った仲間が射殺される。車でペーチャとアン逹は猛スピードで逃走するが、車は横転する。
何とか２人は家に帰り、アナは呆然と椅子に座る。ドアの裏にKGBのアレクセイが隠れていて、ペーチャを射殺する。アレクセイはアナが海軍へ応募したのを見て、KGBのスパイにスカウトする。アナは裕福な軍人の家に生まれ、チェスが得意で、頭がよく精神力もある学生だった。両親が交通事故死し、どん底に落ちていた。アレクセイは、このクソみたいな生活を続けるか、新しい人生を歩むか、すぐに選べと言う。
アナは、どこに行っても結局一生飼い殺しされると、ナイフで手首を切る。アレクセイは５年で自由にすると説得する。アナは、手首の出血を押さえてKGBのスパイになることを決意する。
訓練を受けたアナは、アレクセイの上司オルガに会う。アレクセイは、アナは家柄がよく、チェスが得意で頭が良く、格闘技や射撃に優れ、訓練の成績も優秀だと報告する。オルガは、ハニートラップにしか使えないと断わる。オルガは小説の一節で例えると、アナはドストエフスキーだと言う。アナはチェーホフの『かもめ』の第１章を暗唱してみせる。オルガはアナの知性と記憶力に驚き、試しに預かると言う。
５分過ぎ、アレクセイはオルガにもう１分待つように言う。アナはボスをフォークで突き刺して殺す。アナが携帯電話を持って外に出ると、アレクセイの車は出た後だった。
KGBのオルガの部屋にアナが来て、男の携帯電話を机に投げる。アナは銃に弾が入っていないことを抗議するが、オルガは道具を点検しないのが悪いと言う。オルガは「災いは予告なく訪れる。」と忠告する。アナは二度とヘマをしないと誓う。
オルガはアナにアパートの部屋を与える。アナが部屋で資料を読んでいると、アレクセイから電話が来てディナーに誘う。アナは資料読みが忙しいので、またの機会にと断る。
モスクワ、1990年。サミーが友人と食事をし、モデルを見つけるのが大変だとぼやくと、友人はイズマイロフスキー市場に行くと良いと教える。
KGBの諜報員が市場に来たサミーを見つけ、オルガはアナに売り場に付くように指示する。諜報員が、サミーが迷っていると報告すると、オルガは誘導するように指示する。市場は混雑してなかなか探せないが、サミーがマトリョーシカを売る女性に気づく。彼女は大学生で、名前はアナ。サミーはアナに、モデルになってパリに来ないか誘う。
パリに来たアナがモデル事務所に着くと、サミーが歓迎し、社長のジョンも期待していた。KGBの諜報員がモデル事務所を監視する。マネージャーが寮を案内する。モデル仲間のモードが何でも力になると言う。マネージャーは早速、明日撮影があると言う。
アナは初めての撮影で、様々な服を着て、ポーズを決め、深夜までかかり疲れて帰る。自分の部屋ではモデルが男を連れ込んでセックスしていたので、モードの部屋に泊まる。
アナは公衆電話でオルガに状況を報告する。オルガは、標的が来月パリに来ると教える。
事務所のパーティが開かれ、社長のジョンはアナに共同経営者のオレグを紹介する。パーティの様子をKGB諜報員とオルガが隠しカメラで監視する。オレグはアナを気に入り、ディナーに誘う。
2ヶ月後、エッフェル塔が見えるホテルで、オレグがアナを口説く。アナはオレグの本業を聞くと、武器商人だった。アナは洗面所の流し裏からサイレンサー付きの拳銃を取り出し、オレグを銃殺する。鞄から書類と携帯電話を奪う。アナは廊下の護衛も射殺し、サングラスを掛けて階段を降りる。廊下でアナの替え玉の女性と交代する。アナは部屋で着替えて黒髪の女性に変装し、警備室の警備員を射殺すると、監視カメラの映像を消す。アナは黒髪で出る。アナの替え玉もホテルを出る。
アナはCIAの取調室で、レナード捜査官からオレグ殺しの尋問を受ける。アナがホテルに出入りする場面をCIAが撮影していた。ホテル内の監視カメラの映像は消去されていた。アナはロビーで待っていたが、オレグが来なかったと証言する。アナはレナードの尋問を切り抜ける。
アナはエッフェル塔近くの公衆電話からオルガに、CIAはホテルの出入りをカメラで監視していたが、アナの説明を信じたと報告する。オルガは、CIAは疑っていると言い、日曜日にモスクワに戻るように伝える。
アナはモスクワのアパートに戻る。アレクセイがアナの部屋に来て、２人は激しくセックスする。
アナはオルガとアレクセイと一緒に、KGB長官のワシリエフに紹介される。ワシリエフはアナに、国家のために貢献しろと言う。アナは約束の５年後に自由にするように願うが、ワシリエフはアナに拳銃を向け、KGBを辞める方法は１つだけだと脅す。ワシリエフはチェスをするように求めるが、絶望したアナはまたの機会にと断る。
アナはパリに帰り、モードが金をためて購入した家に行く。モードはアナを歓迎するが、アナは散歩に行く。アナは盗んだ携帯電話でアレクセイへ電話し、アレクセイに「私が自由になる道があったら、手伝ってくれる？」と頼む。アレクセイは「最善を尽くす」と答える。モードの家に帰ったアナが悩んでいると、モードが慰める。
ミラノ。アナは２人のモデルと撮影しているが、５時になっても撮影が終わらない。苛立ったアナはカメラでカメラマンを殴って馬乗りになり、カメラマンの顔を撮影する。
アナは急いでKGBの車に乗る。今回の標的はポーランド大使館のドイツ外交官のヴェルテンベルグで、彼の唯一の弱点は女だ。アナはオルガが待つホテルの部屋で黒髪のカツラを被り、娼婦に変装する。オルガは、鞄と鍵と書類と指紋を奪うように指示する。
娼婦姿のアナは男の部屋に行き、バスルームの流しの下からサイレンサー付き拳銃を取り出すと、ヴェルテンベルグと護衛を銃で撃つが、空砲だった。アナはCIA隊員に捕まり、手錠を掛けられ、腕時計が落ちる。レナードが現れ、KGBを裏切ってCIAのために働くか、怪しまれないように5分以内で選択するように迫る。アナはどうせ自由になれないと言うと、レナードは３年で自由を与えると言う。アナは１年で自由になり、ハワイに住みたいと提案する。レナードは了承し、手錠を外す。アナが何故ばれたか尋ねると、レナードは、鞄の掛け方が違うと教える。
部屋を出たアナは、廊下の壁にもたれて呼吸を整え、オルガの部屋に戻る。オルガはなぜ12分も掛ったか尋ねると、アナは抵抗されたと答える。アナは鞄を出すと、オルガが人差指はどこだと尋ねる。指紋とは人差し指だった。
アナはレナード達がいる部屋に戻り、あの男の人差し指がいると言う。レナードはCIA隊員にヴェルテンベルグを押さえつけさせ、アナがKGBの方法で指を切り落とす。
アナは男の人差指を持って来て、オルガは満足する。アナは疲れたので家で休みたいと言い、涙を流す。オルガは１週間の休暇を与え、モードと旅行に行くように勧める。
アナとモードはホテルのプールサイドで日光浴をする。男が2人に声をかけ、モードが追い返す。モードは先に部屋に帰る。
アナは離れた部屋に行くとレナードがいて、様子を見に来たと言う。レナードは、ディナーの約束をしても実行できない。米国は君を守り抜くと言う。
外でアナとモードが夕食を食べていると、離れた席でレナードが見ている。アナにモスクワにいるオルガから電話が来て、アナの様子を監視していると言う。
夜、モードが寝ていると、アナは部屋を抜け出してレナードの部屋に行く。アナは、「ディナーできないので代わりに寝て」と言って、服を脱いでレナードのベッドに入る。
休暇が終わったアナは、鉄橋下のオルガが待つ車に乗る。オルガは休暇を楽しんだか聞くと、アナは土産の絵葉書を渡す。オルガは仕事に戻れと言う。
アナはエッフェル塔の前を歩き、車で待つオルガにデータを渡す。オルガはアナによくやったと褒め、長官が会いたがっているので、来週モスクワに戻るように言う。オルガは運転手を車から出すと、アナにCIAと接触しただろうと言う。ヴェルテンベルグを撃って部屋に戻った時、腕に手錠の跡があり、その時腕時計を落としたと言う。ここだけの秘密にするので、計画を全て話すように命令する。
アナはホテルの部屋でレナードに会い、２人は激しくセックスする。部屋をCIAが監視していた。レナードはアナに、「CIAとKGBは互いに尊重してきたが、ワシリエフは長官になって関係が悪化した。５年前に9人の部下を失ったが、ワシリエフの指示だった。３年掛けて計画した作戦で、ワシリエフを暗殺し、秩序を取り戻す。成功すればアナはすぐハワイに行ける。」と話す。レナードもアナを脱出させるために、モスクワに行くと言う。レナードは鞄を持って出かける。アナは、レナードの鞄からハードディスクをコピーしていた。
レナードから聞いたアナは、オルガにワシリエフ長官の暗殺計画を話す。オルガは、作戦を実行したらアナに自由を与えると約束する。
KGBの物置で、アナとアレクセイが激しくセックスする。物置からアレクセイが出ると、アナは物置の隅から銃を取り出す。その後アナも出て、一緒に長官の部屋に向かう。
長官室でワシリエフとアナがチェスをし、脇でアレクセイが見ている。ワシリエフはアナに勲章を与えると言う。アレクセイが見ていると、テーブルの下のアナの手が怪しい動きをする。アナは「詰み」と言って、拳銃でワシリエフを射殺する。アナは驚くアレクセイに銃を向けて伏せさせ、アレクセイの首に注射して、眠らせる。アナはワシリエフのパソコンにメモリを差し、データをコピーする。アナは自分の資料の中に、オルガ宛のメッセージを録画する。アナはアレクセイの銃とワシリエフの銃も奪うと、部屋を出る。
KGBの玄関前でレナードがCIAの車で、アナが出てくるのを今か今かと待つ。KGBの警備員がレナードの車に駐車違反なので退くように言うが、外交官車だと言って粘る。
アナは軍人を避けて廊下を歩く。アレクセイが目を覚まし、麻痺した体を何とか動かして、机の下の非常ボタンを押す。隣の部屋のワシリエフの秘書が非常ランプに気付き、ワシリエフが殺害されたのを見る。館内に非常ベルが鳴り響き、軍人がアナを探す。アナは廊下で軍人を射殺しながら進み、資料室の軍人を射殺しながら階段を飛び降りる。地下通路を進むと多数の軍人に襲われるが、格闘しながら手持ちの銃や相手の武器を奪って倒し、出口に向かう。閉まりかけたシャッターにボンベを挟み、アナを止める軍人たちと格闘しながら、シャッターの下をすり抜け、シャッターを閉める。
KGBの建物にサイレンが鳴り響き、レナードは警備員に命令されて車を出す。レナードはアナを心配する。
外に出たアナは、オルガの車で脱出する。
CIAの部隊がモードの家に入って来て、モードに銃を向ける。レナードはモードにアナの居場所を聞くが、モードは何も知らない。レナードは「アナから接触があったら連絡してくれ」と去る。
ニューヨーク。レナードをCIA職員が、ワシリエフ殺害作戦は完璧だったと褒めたたえる。KBGでは、長官を誰にするか思案中だと言う。レナードはアナの行方を心配する。レナードのポケベルに「月曜午後２時、パリ、モンソー公園、スナック・バー」とアナから連絡が来る。レナードはアナが生きていたと喜ぶ。
レナードは公園に行く。CIA職員が公園のあちこちで見張り、ワゴン車の中から監視カメラの映像で警戒する。レナードが指定された店のテーブルに座ると、隣のテーブルにアレクセイが座っていた。アレクセイが隣は何者か連絡すると、やはり公園を監視しているKGBのオルガが、CIAのレナードだと教える。異様な緊張がはしり、レナードはこの場から離れたいと連絡する。CIAの部隊が、レナードを救出に公園に入ろうとする。公園にアナが現れ、レナードは部隊を止める。
アナはアレクセイにキスし、レナードのテーブルに連れてくる。アナはレナードにもキスする。アナは２人にお別れに来たと言う。アナは本当の自分が何なのか分からなくなったと言う。
アナはアレクセイに、ワシリエフのパソコンのデータをコピーしたUSBメモリを渡す。レナードには、レナードの鞄からコピーしたハードディスクを渡す。アナは「このデータを返すから、私を自由にして」と2人に言う。レナードは「君に何かあったら、このデータが公表される訳だな」と言う。アレクセイは「半年経ったら使い物にならない。君の安全も保証できない」と言う。アナは「今まで自由が無かった。半年は永遠も同じ」と答える。アナはアレクセイに「私が自由になる道があったら、手伝ってくれると約束した」と言うと、アレクセイは「違う、最善を尽くすと言った」と答える。
レナードとアレクセイはデータを手に取り、アナを解放する。アレクセイは「落ち着いたら家族の元へ行け」と言うと、アナは「家族はこの２人だけ」と言って立ち去る。
オルガは「そうはさせない」と呟くと、監視所を出てアナを追いかけ、アナに銃弾を浴びせる。銃声が響き、アレクセイとレナードはお互いに銃を向ける。レナードは「彼女を助けたい」と言うが、アレクセイは聞かない。２人の周りに、待機していたKGB職員とCIA職員が集まる。一触即発の中、重装備のCIA部隊がレナードを連れていく。
殺されたはずのアナは茂みに隠れると、アナそっくりの死体を転がす。レナードはワゴン車に戻って監視カメラから、アレクセイは監視所に戻って双眼鏡で、警官がアナの死体を運ぶのを見る。
アナは下水道で服を着替え、カツラを取ってスキンヘッドになると、川辺を歩く。
オルガがKGB長官の椅子に座る。パソコンでアナの情報を見ると、アナからメッセージがあった。オルガがアナに、ワシリエフ長官を殺すように命じたとき、アナは保険のため隠し撮りしていた。アナは自由になるため、自分の情報を消すように求める。オルガは満足そうに「ビッチめ」と呟き、アナの情報を削除する。