The game is set in 1969, 10 years after the original. The game begins with a KGB slide show meeting showing that Cryptosporidium-137, is now deceased for unknown reasons. His clone, Cryptosporidium-138 (Crypto for short), made of more pure Furon DNA, is now taking his place and continuing to pose as the United States President. KGB intelligence reveals that Crypto-138 is the first and only Furon to have genitalia, referred to only as "The Package". Seeing the Furons as a threat to the Soviet Union, the KGB destroy the Furon Mothership with a nuclear missile.
Soon after, Crypto's new adventure begins. Not only must Crypto stop the KGB from destroying America, he desires revenge for the destruction of the mothership. Crypto's commander, Orthopox, downloaded a copy of his consciousness into a holographic unit (called a Holopox) just before he died. The unit projects a hologram of Orthopox and possesses a copy of Pox' consciousness. The Soviets, under the control of Ivan Oranchov, are planning to destroy Bay City using Revelade, a new health drink promoted by hippie guru Coyote Bongwater. Crypto defeats Bongwater and manages to prevent Revelade from being dispersed, before attacking the KGB base, a prison island in the center of the bay.
After saving Bay City from nuclear annihilation at the hands of the Soviets, Crypto discovers that the KGB have fled to Albion and promptly follows.
In the British city of Albion, Crypto meets Reginald Ponsonby-Smythe, the James Bond-esque head of M16 (a parody of MI6), and a rogue KGB agent named Natalya Ivanova. They discover that the KGB have created a type of spore that causes humans to mutate into monsters. Eventually Ponsonby betrays Crypto, revealing he is the leader of the British branch of Majestic, Majestic Command 16. After killing Ponsonby and puzzling over his cryptic reference that the Furons may not be the only aliens on Earth, Crypto learns that the KGB have a base on Takoshima Island.
Arriving in Takoshima, Crypto has to rescue a man named Dr. Go! (a parody of Dr. No) from the Black Ninjas and KGB. He provides access to the KGB base hidden in the island's volcano. Inside Crypto and Natalya are addressed by the mastermind behind the spore plot, Soviet Premier Milenkov. Milenkov shows a film clip of his men using spores on a Takoshimese intern, who transforms into a giant Godzilla-like monster called "Kojira". After defeating Kojira, Crypto follows Natalya to Tunguska, home of "Project Solaris."
In the USSR, Crypto discovers that another alien race has crash-landed on Earth. They are the Blisk, the enemy that the Furons had thought they defeated during the Martian War. Pox realizes that the Tunguska event of 1908 was actually a downed Blisk warship crash-landing into the Tunguskan hillside, not a meteorite. After destroying the crashed Blisk warship and rescuing Natalya from a Blisk gas bubble, Crypto meets Milenkov face to face. Milenkov then retreats to his moon base, Solaris, in a Blisk shuttle.
On the moon, Crypto discovers that Project Solaris is actually a Blisk superweapon designed to bombard the Earth with Blisk spores and radiation, granting the Blisk control of Earth as their new irradiated, water-logged homeworld. Using his ability to "body snatch," Crypto disguises himself as Soviet cosmonaut Leonid, the head scientist on the moon, and convinces the rest of the humans to go to war with the Blisk. Then Crypto manages to sabotage the weapon's firing mechanism. Upon doing so, Milenkov confronts Crypto. He then reveals that ever since the Blisk crashed, they have been controlling the Russian government, each Premier before him had been a Blisk, and they were responsible for several world crises, including the Cold War. After their conversation, Milenkov leaves. Crypto and Natalya battle for their various species to save the Earth by attacking and successfully destroying the Blisk Hive with the O.M.G.W.T.F. Virus Pox developed in his lab, but after the last battle, Milenkov shoots Natalya in the back the moment she was going to kiss Crypto and then Milenkov reveals his true form, a heavily-armored Blisk.
After defeating Milenkov, Crypto relaxes in his Saucer while Pox appears on the video monitor, congratulating Crypto and eagerly anticipating his newly-cloned body. He has detected activity in the emergency cloning lab. He questions Crypto about it, then realizes that Crypto has cloned Natalya, and is extremely infuriated by this and begins yelling at him, just before Crypto abruptly shuts off the video monitor mid-sentence. Lying next to him, Natalya awakens briefly and favors Crypto with a smile and an invitation to wake her "in time for re-entry." As the game ends, Crypto leers at the player and admits to having made "a few adjustments," and sips on a martini.
- Natalya Ivanova - was a KGB agent who went rogue after strange things begin to happen. She allies with Crypto in order to save both their species from Milenkov and the Blisk. She is killed at the end of the game, but Crypto reclones her. It is revealed in Big Willy Unleashed that they had a son. In an in-game conversation, Pox reveals that her clone died about six years before the events of Path of the Furon due to human clones having a short lifetime. She is located in all of the invasion sites that Crypto goes to.
- Agent Ivan Oranchov - he was a commanding KGB officer, and was in charge of the KGB operations in Bay City and Albion. In a final duel with Crypto, he uses Blisk spores to transform himself into a humanoid Blisk mutant, but is ultimately killed.
- Reginald Ponsonby-Smythe - Secretly, the leader of the Majestic Command in Albion. He helps Crypto in two missions, but then betrays him. He is killed by Crypto after he escapes. He speaks with a posh British accent and wields an umbrella rifle. It is discovered through mind-scanning Ponsonby or listening to his speech during his final battle, that he was in love with Silhouette from the original game.
- Milenkov - The Premier of the Soviet Union. He is the main antagonist of the game and is secretly the Blisk leader.
- Blisk - The aliens that the Furons destroyed in the Martian War. Pox describes them as "brutes with large claws and withering halitosis" and the result of "a cockroach mating with a lobster." They have a single hive mind, and are attracted to radiation, as it nourishes them. They are located in the Soviet Union and on the Soviet Moon base, Solaris.
- KGB - The original enemies of Destroy All Humans! 2 until the Blisk are discovered. KGB commanders include Agent Oranchov, Sascha Soysorski, Soviet Premier Milenkov, Blazitsky, Zablazitsky and Leonid. The KGB base: in Bay City is The Rock, in Albion is the abandoned tunnel network (as well as M16), in Takoshima is the volcano as well as a single building in the city, in Tunguska is the large KGB Base, as well as acting as the police when the alert level is raised and on the moon is Solaris.
- Majestic Command, Sixteenth Sector - The British Majestic, controlled by Reginald Ponsonby-Smythe and ultimately Her Majesty. If a British Majestic agent (or Secret Agent) is manipulated by Crypto's psychoknesis, then they will quote "I bet Blofield put you up to this." or "I haven't got a license to levitate!"
- The Freak - The Freak is a hippie in Bay City who knows everything about what is happening. He apparently finds out by picking up radio transmissions with his teeth. By reading his mind, you find out that he sometimes thinks things such as "I am a fish! I am a fish! I am a fish...." or "I AM THE KING OF THE LIZARDS!". It is revealed by reading his mind that all of the other hippies avoid him unless it is to buy drugs from him.
- Coyote Bongwater - A hippie commune leader dedicated to overthrowing "the Man" and the creator of Revelade. Initially working with the KGB to accomplish this, he regrets this decision when he finds out they have betrayed him and actually want to destroy America outright. One of his plans involves using blimps to spray Bay City with Revelade and dumping it in the water supply. Crypto subsequently assassinates Bongwater, halting any other plans he might have had and ending the hippie rebellion.
- Dr. Go! - A Takoshimese scientist that knows much about the KGB and Black Ninjas. He is allied with the White Ninjas and Crypto.
- Agent Sergei - Natalya's former lover who provides information for her, Crypto hates him because of his own feelings for Natalya. Sergei, however, does not share Crypto's hatred; contrarily, he understands Crypto's feelings for Natalya, but looks down on him as though he were a young child. After being infected with Blisk spores, Sergei is never heard from again.
- Gastro - The janitor (and cook) aboard the mothership, he downloaded himself onto a Holopod, like Pox, to survive. Later found as a Datacore and used as a weapon. He apparently had a large collection of Furon folk music before the attack on the Mothership.
- Sgt. Fauxhall - A Military sergeant who has Crypto do a couple of jobs for him, like capturing Clayton Cartwell Jr. (an AWOL hippie who wants to avoid the draft) and kill a rogue military soldier, Private Danza who is selling bazooka crates to the KGB. All is well for Fauxhall until a KGB agent tells a disguised Crypto to kill him and retrieve the bazooka crates.
- White Ninja Leader - The leader of the White Ninjas. He and his group originally wanted to be black but the other ninjas put their order in first when grey was no longer being made. This sparked a war between them. The White Ninja Leader and his men worship Furons and are the "good guys" of the ninjas. He seems to be a little eccentric, judging from the fact that he kidnapped a girl from the super market and was going to sacrifice her, and thinks it's okay because of what Crypto did to Miss Rockwell in the first game.
- Black Ninja Leader - The Black Ninja Leader and his men ignited the war between them and the White ninjas by putting their order in first for black clothing when grey was not made anymore. He and his men are in league with the KGB and are the "bad guys" of the ninjas, like how they attack civilians, cops and the Military. The Black Ninja Leader is the person who orders a disguised Crypto to kill Shama Llama.
- Yamanosuke Hiroto - Leader of the West Yakuza. To differ from the rest of the West Yakuza, Hirotaro wears a peace sign on his suit. He gives a disguised Crypto one mission to lure Kenji Mojo, leader of the East Yakuza into a trap, because Kenji said "His wife was prettier than Yamanosuke's." However, because of a West Yakuza snitch, Kenji Mojo isn't killed. Yet. Hirotaro orders Crypto to kill the snitch, but he still wouldn't feel better. After Crypto kills the snitch, he goes to a KGB agent disguised as one himself to be told to kill both Yamanosuke Hirotaro & Kenji Mojo.
- Kenji Mojo - Leader of the East Yakuza. When Kenji Mojo tells Yamanosuke Hirotaro his wife was prettier than Tojo's, Hirotaro, enraged, orders a disguised Crypto to call Kenji to come to a meeting with him as a set up to kill Kenji. But Kenji is one step ahead of his nemesis, because a West Yakuza traitor tells Kenji the entire plan and he escapes death. The West Yakuza traitor however, is killed by Crypto because he's a rat. When Crypto gets a mission from a KGB agent to kill the 2 Yakuza leaders, Kenji Mojo, along with Yamanosuke Hirotaro is killed.
- Prudence Kane - Prudence is Coyote Bongwater's girlfriend who tries to get everyone to love Revelade because she firmly believes that Revelade will change the nation. She can be killed while the only time she is there after her Revelade meeting.
Crypto can now body snatch humans, using them as a disguise. In addition, new weapons are unlocked by finding datacores ejected from the mothership before it was destroyed.
New Saucer landing points are unlocked by completing the challenges of the ancient Furon god Arkvoodle. The player is now able to call the Saucer from an empty landing site in order to eliminate back tracking, and it can now cloak for limited periods of time. In addition, the Abducto Beam actually abducts humans into the Saucer for usage in the Gene Blender, which upgrades Crypto's abilities.
Destroy All Humans! 2 has a co-op multiplayer mode, so the player can play through the story mode, free roam together and minigames, such as PK Tennis and Duel, with a friend.
The new "Free Love" feature enables Crypto to momentarily force his victims to groove to psychedelic music, thus making them forget they saw him. The new ability called "Mind Flash" mentally stuns everyone in the world for a brief period of time. The Jetpack has a longer lasting battery.