Destroy All Humans! En route vers Paname !

L'histoire du jeu se déroule en 1975, cinq ans après le précédent volet. Le joueur incarne Cryptosporidium 138, un extraterrestre de la race des furons provenant de la planète du même nom.

L'histoire commence dans la ville fictive de Las Paradiso (basé majoritairement sur la ville de Las Vegas) où Cryptosporidium 138 (surnommé Crypto) mène la belle vie après avoir fondé un casino nommé Le poussière cosmique. Le jeu débute avec un didacticiel où il faut faire chanter Murray, un employé de Crypto étant en réalité un espion à la solde des frères Molinari, mafieux et directeurs du casino Palazzo Nero. Pendant le didacticiel, le joueur apprend à se servir de l'arme basique, le Zap-O-Matic, et des pouvoirs psychokinésiques de Crypto. Après avoir fait parler Murray, Crypto se dirige vers l'extérieur du casino où il doit empêcher les mafieux des frères Molinari d'entrer dans son commerce. À la suite de cette courte bataille, Orthopox 13, le "Mentor" de Crypto surnommé Pox par ce dernier et ayant été réduit à la forme d'hologramme après avoir péri dans l'explosion de son vaisseau mère, lui donne la seconde arme basique du jeu, la Sonde Anale. Après quelques missions, le joueur obtient une nouvelle soucoupe et quelques armes. Alors qu'il parle avec Pox dans le stationnement de son casino, croyant avoir gagné contre les mafieux, des extraterrestres apparaissent et Pox. Après avoir battu cinq guerriers Nexos, un char d'assaut apparaît et tire sur Crypto et Pox qui se déplacent In Extremis et se dirigent à la soucoupe où Pox annonce à Crypto qu'il doit détruire la ville à son grand désarroi.

Après Las Paradiso, Crypto va à la ville fictive de SunnyWood (basé majoritairement sur la ville de Hollywood). À la suite de celle-ci, Crypto passera à travers trois autres sites d'invasion : ShenLong (Hong-Kong), Paname (Paris) et la planète Furon. À travers ces derniers, le joueur fera la connaissance du Maître, un vieux furon exilé sur Terre, qui sera tué par son apprenti, Saxon.