It's the early 1960s and Allen Quimp (DOUGLAS MCGRATH) is a henpecked high school grammar teacher whose wife, Daisy (SIGOURNEY WEAVER), wants the better things in life that his current job can't provide. After her father puts pressure on him to get a better job, Allen decides to make up a lie to get both of them off his back. Inspired by the sight of several letters on a robe, he comes up with the fib that he's really working undercover for the CIA and that the fact that he's the last person anyone would confuse for such a person means he has the perfect cover.
Although sworn to secrecy, Daisy soon informs everyone in town about her husband's "real" job, eventually causing Russian ballet dancer Rudolph Petrov (RYAN PHILLIPPE) to come to him to defect. While the CIA is upset that Allen is impersonating one of their agents, they decide to make him a real one so that they can take credit for Petrov's defection. Accordingly, they then decide to send him to some third world backwater where he'll be out of sight. Thus, he arrives in Cuba, where CIA Officers Fry (DENIS LEARY) and Lowther (WOODY ALLEN) inform him of the current political climate, which they see as benign despite the growing turbulence and instability.
After accidentally learning the identity of a double agent the "company" has been looking for over the past several years, Allen is suddenly the hot topic of conversation, a point that pleases Daisy to no end since she's writing a novel about her husband's secret life. Things become more interesting when Allen meets a rogue agent, Crocker Johnson (JOHN TURTURRO), who has the recently overthrown dictator, Fulgencio Batista (ALAN CUMMING) in tow.
Johnson seeks to undermine and remove Cuba's new leader, Fidel Castro (ANTHONY LAPAGLIA), from office and wants Allen's help. From that point on, and as we see some of the ensuing events in flashback as Allen testifies in hindsight in front of a secret Senate hearing headed by a disbelieving Senator (JEFFREY JONES), Allen, Johnson and Batista then attempt various schemes to overthrow Castro, eventually leading to their involvement in the failed Bay of Pigs invasion.