In a large city, giants "Butt-Kong" and "Beaviszilla" are fighting over the same girl that Butt-Kong abducted from a window. A subsequent fight reveals this to be a dream of Butt-Head's, which he is awaken from by a distressed Beavis. It turns out that while they were sleeping, their beloved television was stolen by some crooks. After noticing a broken window, footprints on the floor, and an open front door, Butt-Head comes to the inescapable conclusion... this sucks.
At first the two attempt to find their TV, but after not finding it in the trash, Butt-Head gets a different idea. They sneak into Highland High and steal a TV from the AV room, only to destroy it while wheeling it down the stairs. Next, they try using the TV in Tom Anderson's RV as he and his wife prepare for a vacation. But Beavis destroys that TV from a Spit Take caused by drinking lukewarm soda.
By midnight, Beavis is desperate to find a TV, and the two stumble across a motel offering full-color TV. After attempting to enter several rooms, they come across one occupied by Muddy Grimes. In a drunken state, Muddy mistakes them for hit men he hired to "do" his wife Dallas in a hit-job for $10,000 plus expenses. Thinking that the use of the word "do" refers to sex, Butt-Head gladly complies, and persuades an initially reluctant Beavis by pointing out how they can use the money earned from the job to buy a new TV. Early next morning, Muddy drives the duo to the airport for the ride of Las Vegas. Beavis makes some small talk with an old lady named Martha, and eventually turns into "Cornholio". Back at Highland, Muddy meets two thugs (who coincidentally are the same ones who stole Beavis and Butt-Head's TV) who reveal that they were the hitmen he had meant to send off to Vegas. Muddy is furious that he sent the wrong people to kill Dallas, and drives off to kill all three.
The next morning, upon arriving at their hotel, Beavis and Butt-Head find Dallas hiding in the opposite room. At first, Dallas offers to double Muddy's original offer if they go back and "do" him. However, this quickly changes when Dallas realizes that the two thought "do" referred to a chance for sex. Suddenly, ATF agents arrive at the hotel. Acting quickly, Dallas plants a stolen bioweapon, known only as the "X-5 Unit", in Beavis' shorts, promising that they can score with her if they meet her in DC. She books them a "DreamAmerica" tour bus, and sends them off. Soon after the teens leave, Agent Flemming arrives to interrogate her. However, he is only able to hold her for a few hours, and lets her go.
It turns out that the tour bus Beavis and Butt-Head boarded is hauling the same tour group that Martha is part of. They make a stop at the Hoover Dam, where the boys enter the control room and wreak havoc that ultimately destroys the dam. Meanwhile, Agent Flemming and his assistant Bork discover security camera proof of them leaving the hotel. Bork explains the extremely dangerous nature of the highly sensitive X-5 unit, which will activate if it is hit hard enough. Convinced that the Hoover Dam's destruction was done to help with their getaway, Flemming declares Beavis & Butt-Head "the most dangerous men in America" and places them on the FBI's most wanted list.
At Yellowstone National Park, one of the rangers recognizes Beavis and Butt-Head from their Wanted poster, and call the police. The duo get on the wrong bus, travelling with a bus full of nuns. They stop at a church, where the boys step into confessionals mistaking them for porta-potties, and give bad advice to confessors. The nuns abandon them at the Petrified Forest National Park in Arizona, where they decide to walk to DC on foot through a desert.
When ATF agents show Tom a picture of the two boys, he admits to recognizing them, and that they were whacking off in his camper. The ATF agents thoroughly search his camper, with Flemming saying he thinks Tom might be involved. Back in the desert, Beavis and Butt-Head come across two former Mötley Crüe roadies, who unbeknownst to them are their biological fathers. The boys spend the night with them, but wake up in the morning to find they've left.
They continue walking in the desert, but the heat makes them dehydrated and weak. Butt-Head sees his life flash before his eyes, consisting of him and Beavis just sitting on the couch laughing. Beavis sees a memory of himself as a sperm cell being pushed into an ovum. Beavis takes a bite of a cactus to try and find water, but starts hallucinating in the style of a heavy metal music video.
Muddy finds the two of them with a shotgun, but after they mention they're going to DC to find Dallas, he keeps them alive in his trunk and drives on. They find a jack in the trunk, which they use to escape on the freeway, causing a massive car pile-up. Flemming and Bork see Beavis and Butt-Head on the news broadcast about the highway disaster and they realize that the two are heading to DC. Flemming suspects the boys intend to either set off the X-5 unit in the nation's capitol, or sell it to a foreigner at an upcoming peace conference.
Beavis and Butt-Head find their original Dream America bus and board it, arriving in DC. They tour the Capitol, but upon leaving without finding Dallas, Beavis goes on an angry rant about how he's never gonna score before getting beaten by the bus driver. Muddy confronts Dallas in a parking garage before she can meet Beavis and Butt-Head. They have sex in his car but are found and arrested by the ATF. Beavis once again turns into Cornholio as they enter the White House. Wandering into the Oval Office, he picks up the red phone, causing a military alert. Butt-Head attempts to seduce Chelsea Clinton but is thrown out of her bedroom window. He is detained and cavity-searched by ATF officers.
Beavis ends up in Tom's camper and starts masturbating to a picture of Dallas before Tom finds him and kicks him out without his pants. The ATF spots Beavis and surround the camper. Just before Flemming is going to give the squad the command to fire, Tom jumps out of the camper with Beavis's pants in his grasp. An ATF agent lunges and tries to yank the pants from Anderson's hold, ripping them and sending the X-5 Unit soaring through the air. The unit lands safely in Butt-Head's hand, who kindly hands it to Flemming. When the squad find the picture of Dallas in Tom's camper, they accuse him of being an accomplice of Muddy and Dallas, and trying to frame Beavis and Butt-Head. Tom is arrested along with Dallas and Muddy while his wife is taken for a cavity search.
Flemming proclaims Beavis and Butt-Head heroes, and they meet President Bill Clinton, who makes them honorary ATF agents. The boys are ecstatic to be in the bureau of "beer, cigarettes, FIRE-arms, and chicks". They return to Highland, upset that they did not get any sex or money. However, they find their TV at the motel, and walk into the sunset carrying it and insulting each other until Beavis suggests going into Anderson's tool shed to masturbate.
