Alex Scott (OWEN WILSON) is a government spy who works for the Bureau of National Security. Jealous of the success and latest gadgets that rival spy Carlos (GARY COLE) receives, and deeply smitten with another spy, Rachel (FAMKE JANSSEN), Alex finds himself assigned to an important mission.
It seems that a powerful arms dealer, Arnold Gundars (MALCOLM McDOWELL), has stolen the military's latest invention, the Switchblade jet. Not only is it the most advanced piece of weaponry on the planet, but it's also invisible to radar, infrared and the human eye, thus making it rather hard to locate.
Fortunately, the super-middleweight boxing championship of the world is going to take place near Gundars' Budapest headquarters and he's planning a party the night before the match. Accordingly, the BNS recruits boxer Kelly Robinson (EDDIE MURPHY) to get Alex into the party so that he can find the plane and prevent Gundars from selling it to the highest bidding terrorist.
Accompanied by handlers/assistants such as Jerry (PHILL LEWIS) and T.J. (VIV LEACOCK), the undefeated and quite egotistical boxer agrees to help, but he and Alex initially don't like each other. Nevertheless, they set out for Budapest where Kelly's planning to box Cedric Mills (DARREN SHAHLAVI), while Alex is anxious to see Rachel who's already there in place.
From that point on, the agent and boxer become an unlikely spy duo as they attempt to infiltrate Gundars' lair, find the plane and complete their mission without getting themselves killed.