Полностью сюжет стал известен только в день начала продаж. После прохождения игры становится понятно, что за годы разработки сюжет кардинально так и не поменялся. Ролики 1998 и 2001 годов демонстрировали Лас-Вегас, пустыню Невады, дамбу Гувера и вагонетки, однако все это изменилось в достаточной степени. Игра начинается в мужском туалете. Дюк мочится, а затем проходит небольшой брифинг с солдатами EDF (Earth Defence Force). Оказавшись на футбольном поле, Нюкем в одиночку сражается с инопланетным императором Циклоидом (Cycloid) и, убив, забивает его вырванным глазом гол (это явная отсылка на финал предыдущей игры).

После победы на экране появляются финальные титры, камера отдаляется и становится понятно, что Дюк играет в видеоигру находясь при этом в своём огромном особняке в компании двух симпатичных близняшек Холсен. Они предлагают Дюку посмотреть их новое музыкальное видео, но неожиданно трансляция прерывается. Диктор сообщает, что над Лас-Вегасом висит огромный инопланетный корабль. Выйдя в холл, Дюк видит его в окно. Пройдя по своему небоскребу в телестудию, Дюк узнает, что съемка телешоу с его участием отменена. Спустившись в свое тайное убежище, Дюк принимает сеанс видеосвязи с генералом Грейвсом и президентом США и получает задание не вмешиваться в происходящее, пока президент пытается вести переговоры с императором Циклоидом.

В здании появляются инопланетные штурмовики и свинокопы. Дюк вооружается и следует к турели, с помощью которой он сбивает инопланетный корабль. Тем временем пришельцы помещают земных женщин в коконы для транспортировки в неизвестном направлении. Пробравшись по своему отелю и казино, Дюк оказывается уменьшенным и часть пути проделывает на игрушечном автомобиле. Вернув свой привычный рост, Дюк защищает от нападения инопланетян своих близняшек, но их всё же похищают, и он отправляется их спасать.

Пройдя несколько разрушенных кварталов, Дюк убивает огромного командира штурмовиков и спускается в подземелье, где пришельцы организовали «Улей», куда транспортируют похищенных женщин и используют для размножения. Не имея возможности помочь несчастным, Дюк вынужден идти дальше, пока не находит своих близняшек, чью смерть он также не в силах предотвратить. Уничтожив несколько десятков коконов, Дюк попадает на ледовую арену, где сталкивается с Королевой (аналогом пчелиной матки у пришельцев). Убив её и вырвав её язык, Дюк теряет сознание от взрыва её внутренностей. Последнее что он видит — подбегающего к нему солдата.

Дюк приходит в себя в собственном стриптиз-баре. Милая девушка предлагает Дюку найти презерватив, попкорн и фаллоимитатор, после чего обещает ему приятную ночь. После того, как он находит все предметы, Дюк оказывается в комнатке для приватных танцев, но неожиданно его видение (оказавшееся просто сном) прерывается, и он приходит в себя на борту вертолёта. Сопровождающий его боец EDF Дилан объясняет, что пока Дюк был без сознания, пришельцы открыли портал над дамбой Гувера. Но прежде, чем они добираются до цели, их сбивают, и главный герой оказывается на крыше «Бургер Дюка». После нескольких стычек с пришельцами он проникает внутрь заведения и, уменьшившись, проходит через затопленную кухню, где помогает неизвестной девушке. Получив оружие-уменьшитель, Нюкем убивает несколько свинокопов и, сбив с десяток летательных аппаратов пришельцев, наконец, отправляется к дамбе.

Под мелодию «Полёт Валькирии» Вагнера в жанре метал, Дюк расстреливает свинокопов на шоссе с борта вертолета. Высадившись, он продолжает путь на бигфуте, но вскоре бензин заканчивается, и ему приходится искать ближайшую заправку. Добравшись до заброшенного городка Морнингвуд, Нюкем в стиле вестерн под музыку кантри расправляется со свиньями и, вновь заправив бигфут, едет дальше. В третий раз за бензином приходится идти в заброшенную шахту. Проехав на вагонетках, Дюк добирается до дамбы, попутно утопив свой автомобиль.

На дамбе Нюкем встречает президента воочию и вынужден выслушать обвинения в свой адрес. Президент негодует из-за того, что главный герой устроил бойню и тем самым сорвал мирные переговоры с пришельцами. Дюк пытается спуститься вниз и перекрыть энергию инопланетянам, но на дамбе появляется огромный военачальник пришельцев, и герой вступает с ним в бой. Победив, Дюк спускается во внутренние помещения дамбы, где несколько раз видит издалека предводителя пришельцев — нового императора Циклоида. Покатавшись на погрузочном каре и задавив несколько свинокопов, Дюк снова уменьшается, проходит через работающий генератор и обесточивает дамбу. Снова увеличившись, он встречает старого работника дамбы, управляющего краном, на котором Дюк вступает в схватку с огромным летающим осьминогом.

Проплыв через затопленные помещения дамбы, Дюк находит смертельно раненного Дилана, который отдает ему взрывные заряды, чтобы подорвать дамбу. Выплыв наружу, Дюк закладывает их под водой у подножия дамбы, где сталкивается с огромной Энергетической пиявкой. После того как она повержена, Нюкем взрывает дамбу и тем самым прекращает подачу энергии в портал пришельцев, который быстро закрывается. Выбравшись на поверхность, Дюк снова встречается с президентом, в ярости отдающим приказ нанести ядерный удар по дамбе, убив оставшихся пришельцев во главе с императором и самого Дюка. Однако прежде чем президент успевает улететь, сам император Циклоид выбирается из-под завалов и убивает его и его охрану. Дюк убивает императора, но несмотря на помощь генерала Грейвса, не успевает выбраться из зоны поражения уже сброшенной ядерной бомбы. Спутниковый снимок показывает гигантский кратер на месте дамбы Гувера, фотографию Дюка и статус — «Погиб в бою».

Однако после финальных титров показывается короткий ролик, в котором Дюк дает пресс-конференцию вскоре после победы над пришельцами. Ему задают вопрос: «Что вы собираетесь делать теперь, после спасения мира?», на который он отвечает: «Хочу стать президентом. Да здравствует король, детка!» На этом игра заканчивается.