Big Willy Unleashed takes place before the events of Path of the Furon. The game is set in 1975, 6 years after Destroy All Humans! 2 (1969). Cryptosporidium 138 and his mentor, Orthopox 13, attempt to support the popularity of Big Willy's, a fast food restaurant Orthopox owns. Pox reveals that the Big Willy food franchise is actually a scheme to dispose of the human bodies Crypto leaves lying around.
Crypto and Pox are watching television and happen upon the evening news. Bill Kincaid, a news reporter, announces that the Big Willy Corporation has opened its five-hundredth restaurant, and that President Huffman has resigned, implying that Crypto gave up on controlling the American Government. The news is then interrupted by the missing heiress named Patty Wurst using a pirated television signal to appear on the channel. She reveals that Big Willy is using human corpses to grind up and feed to the public and that a shipment of meat supply is going to dock at Harbor City to prove her case.
After Crypto kills Patty Wurst, in the new Big Willy mech, Pox figures out that his actual enemy is Colonel Kluckin, the owner on a competing fast-food restaurant, and that he might be a threat to the Big Willy franchise.
Pox sends Crypto to Fairfield, home of the new Big Willy restaurant, to see if he can find a lead to where Kluckin might be hiding. After Crypto lands, Pox notices that a group of Roller Girls skate out of the Big Willy restaurant holding a briefcase. Inside is the secret recipe for the Big Willy fast food. Crypto finds them in the back of an alleyway; he destroys all of them except for Mindy Peters, their leader that somehow manages to hide. Later, she appears in front of Crypto and tells him that the Furon species and the Big Willy franchise will be brought down. Attacking Crypto, she escapes. Pox informs Crypto that his weapons and jet pack are broken. He returns to the saucer and cripples the Roller Girls' operations. Afterwards, Crypto body snatches the Corncob King, the boyfriend to Mindy Peters. He meets her at a phone booth, after which he jumps out and electrocutes her to death. Pox orders Crypto to destroy all of Fairfield (except for his restaurant) to wipe all traces of evidence that could smear the Big Willy name and head off to the next area.
Pox brings Crypto to Fantasy Atoll, an Island located near Malaysia, as a tactic to beat Colonel Kluckin. There, Crypto meets Mr. Pork, the man who ran the island, and Ratpoo, his servant. Mr. Pork promises Pox a new body and Pox agrees to his offer and temporarily gives up on their mission. Crypto must find parts to build a new body, but it turns out to be a hoax and it blasts Pox somewhere on the other side of the island. Crypto finds the module broken. A Furon Customer Support representative instructs Crypto on how to repair the damaged Holopox unit, Pox is then restored and wants revenge. Crypto hypnotizes Ratpoo, who grabs Pork and throws themselves into the volcano. To their surprise, Mr. Pork survives and attacks with the Hate Boat, a giant warship. After destroying the Hate Boat, Pox and Crypto go to Vietmahl to find Colonel Kluckin.
In Vietmahl, Kluckin reveals that he has been carting off corpses from the Vietmahl war into meat for his restaurants, copying Big Willy's meat idea. Crypto and Pox confront a Big Willy employee named Trahn, who turns out to be a double agent for Kluckin. After successfully completing several objectives, including killing Trahn, Crypto climbs inside the Big Willy mech and manages to defeat Kluckin in a robotic Vietmahlese temple god. However, upon defeating Kluckin, Pox claims that he's done with fast food. Though angered by Pox for abruptly giving up on the restaurant after just now defeating Kluckin, Crypto gleefully takes the profits from the restaurant and tells Pox that he will make the business transactions from now on and that has an idea for their newly acquired money that involves a "little town in Nevada", as the both of them walk off into the distance.
- Colonel Kluckin - A parody of Colonel Sanders, this southern restaurant tycoon owns and runs "Kluckin's Kitchen," a parody of KFC. After many scuffles and run ins with Crypto, he faces his nemesis in Vietmahl in a mechanical version of a rain forest god and subsequently, he is killed as Crypto (in his Big Willy robot) managed to destroy his robot after the intense battle. He is a parody of Colonel Sanders.
- Patty Wurst - Fashion Supermodel billionaire heiress, turned militant activist anarchist, Patty Wurst, a parody of Patty Hearst, has flair for metaphorical vagaries and misguided social causes. She is defeated by Crypto in his Big Willy robot going against him in a giant combat tank.
- Mr. Pork - This benevolent owner of Fantasy Atoll has a special medallion made that protects him from Furon weaponry, and also a tall, and faithful, assistant named Ratpoo. Pork is defeated after the death of Ratpoo and the destruction his battleship, the "Hate Boat".
- Mindy Peters - Mindy is the leader of a gang of Roller Girls armed with antique Furon D-rays. She also has diamond studded brass-knuckles, and her disco ball can blind people. She is vaporized after Crypto disguises himself as an attractive human male (known as the Corncob King) and leads her to her doom.
- Trahn - Trahn is a Vietnamese that works with Pox in Vietmahl until it is revealed that he is a double agent, and actually works with Colonel Kluckin. He is eventually killed by Crypto.
- Blastomycosis (Blasto for short) - A Furon child with features of a human. Little is known about him, except that when Crypto is doing certain jobs, he makes his appearance, showing an ion detonator in his hands and firing a bomb from the detonator to blast a human or a group of humans before taking off. It is later discovered that Blasto was, in fact, the son of Cryptosporidium and Natalya Ivanova. This revealed Crypto and Natalya did have sex in the end of Destroy All Humans! 2, but was originally created by Crypto, who tampered with Natalya's DNA in the cloning chamber.
- Toxoplasma Gondii - A snobby bureaucrat and Furon Efficiency Expert who hails from the Furon homeworld, Gondii puts Crypto through a series of tests designed to prove Crypto's invasion skills while at the same time breaking his spirit. When it is eventually discovered that Gondii is a fraud, posing as an efficiency expert and trying to get Crypto's spirits down so that he can steal their DNA harvesting operation, Crypto and Pox seize the chance to destroy him, and notify the homeworld, so that his clone would be transferred to Gorta's Prison Moon.
- Big Willy - Big Willy is the mech disguised as the Big Willy mascot, used in the game to help protect the restaurant from it's enemies. It is the only other pilotable Furon vehicle in the series, other than the Saucer.
In Big Willy Unleashed the player can play Co-operative or Competitive mode. In co-operative, the goal is to protect Big Willy's restaurant and destroy Kluckin's Kitchen. In competitive mode, the player must touch the beacons and kill each other. The player can play two areas in co-op and compete mode.