Max, an analyst for the top secret American intelligence agency CONTROL, yearns to become an agent like his friend Agent 23, whom he idolizes. Despite scoring extremely well in the acceptance tests, Max is denied the promotion as the Chief (head of CONTROL) feels that Max’s analytical skills are best used for his present assignment. When CONTROL headquarters is attacked by its arch-enemy, the terrorist organization KAOS, (led by Siegfried, in retaliation for CONTROL's infiltration of KAOS.) almost all of CONTROL's agents' identities are exposed, leaving only Max and Agent 99, whose recent plastic surgery has protected her identity, to pursue the culprits whilst former field operatives such as 23 are demoted to desk jobs. Max is promoted to field agent status with the codename Agent 86, but the experienced 99, who views the naive and bumbling, but overwhelmingly enthusiastic Max as an irritating encumbrance, is reluctant to partner with him. Before he leaves HQ, two of Max's friends and lab men give him an unusual Swiss Army Knife which not only has the standard equipment, it also comes with a flamethrower and a crossbow that fires harpoons.
After a series of mishaps while traveling on a commercial airliner, Max and 99 enter Russia by parachute (albeit with a slice of difficulty), hoping to trace KAOS’ recent acquisition of nuclear materials through its chief bomb maker, Krstic. Along the way, they are attacked by Dalip, a formidable henchman of Siegfried’s. By infiltrating a luxurious party hosted by Krstic, they trace the nuclear material > uranium to a KAOS nuclear weapons factory disguised as a bakery, but Max is forced to shoot Krstic when he and his men corner them. In the bakery, Max meets with Siegfried and his second-in-command, Shtarker, only to learn that Siegfried was expecting him; a double agent has compromised his and 99's identities. Max manages to escape capture and bombs the weapons factory. During their escape, Max and 99 are confronted by Dalip; realizing that he knows Dalip through hours of listening to him on spy ‘chatter’, Max manages to persuade Dalip to spare their lives by giving him advice on how to repair his failing marriage. The Chief sends 23 to observe the clean-up of the factory, but KAOS manages to sneak the weapons out through the Moskva River, leaving 23 to report that only a bakery has been destroyed. Realizing that Max was alone during his key discoveries, CONTROL believe Max to be the double-agent; 99, who has been gradually falling in love with Max through their shared experiences, is heartbroken but takes Max into custody. CONTROL becomes a laughing stock in the intelligence community. Their warning is disregarded when Siegfried threatens to release nuclear weapon detonator codes to rogue states unless the United States government pays him $200 billion.
While Max is in a CONTROL holding cell, Dalip sends him a coded message via the radio show American Top 40 revealing Siegfried’s plan; as a ‘demonstration’ he intends to detonate a nuclear device during the President’s visit to a concert performed at the Walt Disney Concert Hall in Lost Angeles. Max escapes from CONTROL, takes items from the original 1960s television series (such as the Shoe Phone, cars, suit and flies to Los Angeles to unite with the Chief, 99, and 23, who have flown out to persuade the President to take the KAOS threat seriously. Although 23 is skeptical, Max manages to convince 99 and the Chief that he is not the double agent. As KAOS plants the nuclear bomb in the concert hall, Max's watch beeps when he's near 23, picking up trace elements of radiation. Max questions him as to why he'd have radiation on him if he said the bakery was clean. 23 tries to cover up by saying that half of Russia is radioactive. Max also points out that 23's knife wound is seeping blood which 23 had previously said happens when his blood pressure rises, concluding that 23 is the double agent and is nervous about having been found out.
23 then pulls out a gun and takes 99 hostage. He tells Max and Chief that if he's followed, she'll die. He flees, forcing Max and the Chief to give pursuit, despite 23's threat to kill 99. They give chase in a limo, but soon hop onto a plane. Max reaches 23's car by jumping out of a plane and rescues 99, but in the struggle the car is set on fire (due to Max's Swiss Army Knife) and forced onto railroad tracks. 23 is distracted when Max follows 99's example during the skydive and kissed 23 to distract him. After the kiss, the car collides with a freight train and 23 is killed. After analyzing 23's Max realizes that the bomb will be triggered by the final note of the song just before the final note. Max is applauded for rescuing the president by every one inside the concert hall. Meanwhile, Siegfried finds that his plan has failed. Siegfried tells Dalip that he will not kill his wife for his failure, though he comments that he would be doing "the sighted world a favor" if he did. In response, Dalip throws him out the car window. It's unknow as to whether or not he drowned.