The movie opens in the tiny country of Pottsylvania, located between the counties WrestleMania and Yoursovania, where Fearless Leader concocts a plan to obtain a time-reversal microchip, invented by Professor Anton Paulovitch. He asks his top agent, Agent X (whose face is obscured), to do the assignment, But Agent X suggests they send some patsies to find Paulovitch. Boris Badenov and Natasha Fatale accept their assignment to find the Professor, and are told to America. After a number of failed attempts to get there (resulting in Fearless Leader having to save them many times), they make it to America, where they are sent to CIA. The head of CIA, Sheldon Kaufman, decides to have tests run on them to see if they are truly defecting. After the test, it's obvious to everyone that they should be deported, but a worker, Willie, points out they hadn't had any defects in a while, and thinks they should play along and in the meantime spy on them to see what they are after.
Boris and Natasha are given an apartment and money, while being watched from a distance by Agent X, who himself is being followed by a mysterious figure. Boris and Natasha have to meet with a secret assassin named Kalishak, who supposedly knows who they should seek, but first have to deal with their next-door neighbors, Toots and Harve, who are very interested in knowing about them. Toots assumes Boris and Natasha are couple, and when Natasha denies it, Toots figures she's wrong. Natasha, who has become a little fascinated with America, also learns from Toots that American couples usually help each other, something Boris and Natasha do not.
They find Kalishak, who denies that he knows anything about the professor. After accepting a bribe, Kalishak acts as a shoe-shine boy and tells Boris "Search your sole", which Boris doesn't understand. After they leave, one of Kalishak's potatoes is replaced with a bomb, killing Kalishak. Natasha later sees information written on the sole of Boris' shoe, telling them to find "Minelli". Disguised as rug cleaners, they go to the location written on the shoe, where they learn that the "Minelli" they're looking for is Sal Minelli, a photographer whose photos hang on the walls, but doses not actually work in that location. Natasha then gets an offer for a photo shoot and a party for it, which Boris figures will be a good opportunity to meet Sal Minelli. To pass the time before the party they go shopping at a mall, but the next day Natasha returns, going shopping with Toots, behind Boris's back. She learns that Toots doesn't need Harve's permission to do things, and learns more about their married life. Boris says a code phrase to many photographers, to no avail, before not being allowed in, But Natasha soon hits celebrity status.
Boris gets annoyed at Natasha for acting like such a celebrity, especially since Fearless Leader had ordered them to keep a low profile. But Natasha remembers what Toots had told her, and points out that's she been responsible for Boris' success, before leaving for a party. Boris starts to feel bad about their argument, while at the party Natasha keeps seeing Boris. She leaves the party, and finds Boris sleeping outside.
Sal Minelli calls their home and arranges a photo session with Natasha. It turns out Minelli is a spy as well as a photographer, and they are being spied on by Kaufman, Agent X and the man who had been following Agent X. He informs her that Fearless Leader ha sent them as patsies and that they'll be killed when they find the professor. Just when he's about to tell her the name of Agent X, Agent X kills Minelli. Boris disguised as a cop, finds out that Agent X is actually Willie. Back at their apartment, Boris realizes that they can trust nobody but themselves, and have to leave. They leave right as an assassination attempt on them occurs. Disguised as overweight Irishmen, they stay at a hotel, where they find Willie dead, and also find that he had an 11:30 train schedule. They leave with Willie, intent on hiding his body, but they encounter Harve and Toots attending a party at the hotel, and convince them Willie has had too many drinks. Boris and Natasha eventually send Willie's body down a laundry chute, only to remember that they had left the train schedule at the hotel room. When they get back, they see Paulovitch, who's revealed to the audience to be the one who had been following Agent X. He asks that they discuss the chip, which Boris and Natasha still know nothing about, but then they get a knock at the door. It's Toots and Harve, who found Willie's body and decide to return him to them. When questioned about being at a hotel when they have an apartment, they have an apartment, they claim that they are there for relationship counseling. Once Toots and Harve are gone, they find Paulovitch missing, along with the train schedule.
They chase after Paulovitch, eventually catching a taxi, where they see Paulovitch and question him, who claims he doesn't know what they are talking about. Boris then discovers lit dynamite in the taxi, and that the driver is actually a dummy. The car explodes, but then the explosion reverses. After a few explosions and reverses, they jump out of the taxi. Paulovitch tells them about the time-reversing chip and reveals that that was his first life-and-death experiment with it. He tells them about the chip, and that his evil twin brother Kreeger is also after it. Boris and Natasha become convinced to help make sure it doesn't fall into the wrong hands, but Paulovitch's talking lasted so long that they fell asleep. Paulovitch gets kidnapped, but Boris and Natasha find a penny, which they instantly see as a clue. They go to Mt. Rushmore, where they notice a ladder going into Lincoln's nose.
There, they find Paulovitch's secret laboratory. They discover millions of time-reverse microchips, and also find Anton tied up. He tells them he was kidnapped by Kreeger, but then they learn that he is in fact Kreeger, while Anton is free. They learn that once Anton realised the microchip could be a bad thing if in the wrong hands, he tried to destroy it, only for its effect to protect it from destruction, so he had them mass-produced, with the intention of sending them to every country, potentially ending wars. Kaufman comes in, but reveals that he's not actually working for the government, but the auto industry and insurance companies, and knows that the chip could put an end to his business. Harve and Toots then show up with guns, but it's revealed that they are secretly Agents Moose and Squirrel. Fearless Leader shows up and takes over, taking the pile of microchips. After Natasha manages to make the power temporarily go out, a fight ensues, then many of them point guns at each other. Boris takes out a stick of dynamite, which he was "saving for a rainy day", and throws it at the pile of microchips, which sends them back to the very beginning of the movie. They are surprised to see Paulovitch with them when he wasn't there at the beginning, but Paulovitch guesses that there was an overload. Knowing what will happen, Boris realises that Fearless Leader must know what will happen as well, so Boris decides they will go to Tahiti (a place Natasha had earlier expressed desire to visit) instead. When Paulovitch realises that he hadn't been properly introduced to them, Boris introduces Natasha as his girlfriend.
The narrarator wonders aloud if they really are safe from the danger they had avoided by going to Tahiti, asking all kinds of questions, before Boris tells him to shut up. The narrarator then tells viewers to tune in to their next episode, "Goodbye Mr. Chips, or The Megabytes Back!"