Destroy All Humans Hikayesi
Bu ortamlardaki tüm binalar ve yapılar yok edilebilir (ağaçlar ve kayalar hariç) ve insanlar Crypto'nun bu yerlerdeki varlığıyla alarma geçebilir. Bazıları kaçarken veya saklanırken, diğerleri oyuncuyla savaşabilir. Grand Theft Auto serisinin aranan seviyesi gibi bir uyarı sistemi, Crypto'nun ne kadar dikkat çektiğini gösterir. Alarm seviyesine bağlı olarak; polis, ordu ve nihayetinde Majestic, sivilleri Crypto'dan korumaya çalışabilir.
Oyun bir Furon, Cryptosporidium-136 ile başlar ve askeri personelin bir roketi test ettiği bir fırlatma sahasının üzerinde gezinir. Roket fırlatılır ve Crypto-136'yı taşıyan gemiyi yok eder ve onu ölümcül şekilde yaralar. Crypto-136 daha sonra ABD Ordusu tarafından ele geçirilir. Bir süre sonra Cryptosporidium-137, başka bir Furon, Orthopox-13 ile Dünya'ya gider. Cryptosporidium (takma adı Crypto) 136'yı kurtarmak niyetiyle gelirken, Orthopox (Pox lakaplı) çalışma için insan beyni saplarını çıkarmak ister. Crypto, Pox'un inekleri Dünya'nın baskın yaşam formu sandığı Güney Amerika'daki Şalgam Çiftliği'ne gelir. Majestic ajansı, Crypto bölgeden geçen bir ordu tugayının büyük bir kısmını yok ettiğinde Furon'un varlığı konusunda uyarılır. Pox, Crypto ile hologram benzeri bir cihaz aracılığıyla iletişim kurar, ardından Crypto'ya insan beyni saplarına ihtiyaç duymasının nedeninin saf Furon D.N.A içermeleri olduğunu açıklar. Furonlar, Furon İmparatorluğu tarafından yaşanmaz hale getirilen Mars'la bir savaşın ardından kıyı izni için Dünya'da durduklarında, çağlar önce Furon izcileri tarafından onlara teslim edilir.
Ortabatıdaki Rockwell kasabasında ve California banliyösü Santa Modesta'da birkaç görevden sonra Crypto ve Pox, Majestic'in farkına varır ve Bölge 42'yi atom bombasıyla yok etmek ve tekrarlayanını yenmek gibi eylemler gerçekleştirerek hükümetin onları durdurma girişimlerini sakatlamaya başlar. Bu yapan kişi oyunun düşmanı, Armquist, ordunun başı olarak geçer. Oyun boyunca, Crypto'nun çeşitli eylemleri hükümet ve medya tarafından gizlenir ve bu da onları ya acayip kazalara ya da Komünizme atfeder.
Union Town'da geçici olarak yakalandıktan sonra oyun, Crypto'nun Başkan Huffman'a suikast düzenlediği ve tüm Kongre üyelerini vahşice katlettiği Capitol City'de doruğa ulaşır. Yakında, ABD hükümeti görünüşte Furonlara teslim olur. Crypto, Capitol'ün önünde Majestic'in lideri Silhouette ile tanışır. Silhouette ile kısa bir sürtüşmeden sonra Crypto, onun bir kadın olduğunu keşfeder. Silhouette, Başkan Huffman'ın beyni tarafından kontrol edilen devasa bir makine olan Robo-Prez'i ortaya çıkartır. Crypto, uçan dairesinde Robo-Prez'i yener ve ardından Octagon'daki son bir savaşta Silhouette'i yener. Silhouette ölürken, dünyanın her yerinde başka Majestic bölümleri olduğunu ortaya çıkarır. Ancak Crypto, Silhouette'in liderliği olmadan Majestic'in Furon'un devralınmasına direnmek için tamamen güçsüz olacağından emin olur.
Oyun, Huffman'ın televizyonda yayınlanan bir konuşma yapmasıyla sona erer ve Amerika'ya, son olayların ABD'nin su kaynaklarını zehirleyen komünistlerin işi olduğu ve bunun sonucunda tüm ülkede insanları zararlı virüslere karşı taramak için test merkezleri kurulduğuna dair güvence verir. Daha sonra insanların, görünüşe göre beyin sapı ekstraksiyonu için Ordu askerleri tarafından isteksizce garip makinelere sürüldüğü gösterilir. Huffman'ın daha sonra kılık değiştirmiş Crypto olduğu ortaya çıkar.