Действие игры начинается в вымышленном городе Нео Cити (Neo City) в 1992 году. Там находится центр оперативного противодействия организованной преступности, именуемый "Contra Force", во главе которого находится человек по фамилии Бёрнс (Burns). Перед оперативниками поставлена задача: уничтожить криминальный синдикат под названием "D.N.M.E". Бёрнсу звонит некто Фокс (Fox), информатор, и сообщает, что неизвестные угрожают руководителю разведки. Бёрнс назначает информатору встречу, чтобы узнать больше подробностей. Однако когда Бёрнс прибывает в порт, где была назначена встреча, выясняется, что Фокс уже мёртв. Бёрнса и его отряд внезапно атакуют вооружённые бандиты. Теперь герои должны очистить город от террористов.

В игре реализовано множество нововведений по сравнению с предыдущими играми серии:
- Появился напарник, управляемый компьютером.
- Главного героя теперь можно из четырёх персонажей, которые отличаются набором оружия, высотой прыжка и скоростью бега;
- Смена оружия происходит путём накопления бонусов;
- Появились самонаводящиеся ракеты;
- Окружение стало более интерактивным: теперь герои могут уничтожать отдельные приборы, ящики и некоторые предметы;
- Влияние атмосферных явлений: ветер сносит в сторону персонажа, бегущего по крылу самолёта.