The episode begins with an announcement that viewers have waited for weeks for the answer to the mystery "Who Is Cartman's Father" but then points out that the answer will not be revealed in this episode; instead there is a presentation of a stand-alone cartoon titled Not Without My Anus starring Terrance and Phillip. A caption wishes the viewers a Happy April Fools' Day. The cartoon itself opens in a courtroom in Canada with Terrance on trial for the murder of a local doctor; Phillip is his lawyer while Terrance and Phillip's sworn nemesis Scott, who has had a long hatred of the duo's toilet humor, is acting as the prosecutor. Scott uses a group of seemingly airtight exhibits to prove Terrance's guilt, while Terrance's defense consists of nothing but a long string of fart jokes. Ultimately, the jury returns a verdict of not guilty. Angered, Scott promises vengeance. He is ultimately approached by Iraqi dictator Saddam Hussein, proposing a deal: Saddam would assist in getting Terrance and Phillip out of Canada, in exchange for Scott assisting Saddam and his Iraqi associates into Canada. Scott is apprehensive about trusting Saddam, but agrees to the deal. The pair then conspires to kidnap Sally, daughter of Terrance and Celine Dion, and hold her hostage, as bait to lure Terrance and Phillip to Tehran; Saddam's soldiers would then murder Terrance and Phillip on arrival.
Terrance and Phillip become aware of the kidnapping when they receive a letter, but they immediately locate Sally upon arrival in Tehran. The duo return Sally to her home, where Saddam has now taken control. Celine, Terrance's now ex-wife, is dating, and has become pregnant by a friend of the duo named Ugly Bob. While the couple discuss their relationship, Saddam interrupts and takes them hostage, with Celine having planned to sing at a game. Scott has also become worried about the presence of the Iraqi soldiers in Canada, but becomes infuriated when he finds that Terrance and Phillip have returned to Canada safely. He confronts Saddam about the double-cross, but Saddam's armed guards scare him into backing away. It is revealed that Saddam is trying to take over Canada as the first step in a plan for world domination. Terrance and Phillip arrive at the game. Instead of following a plan set up by Scott to commit suicide by using a bomb, they come up with a new plan and put on gas masks. With brute force, everyone farts a huge gas cloud which kills Saddam and his soldiers. Scott arrives and is annoyed to find that Terrance and Phillip are still alive. Terrance, Phillip, Celine and everyone else (excluding Scott) celebrate their freedom with a rendition of "O Canada". During the credits, an announcement is shown stating that the solution to who Cartman's father is will be answered in a few weeks.