Colonel Bassad, a dictator of a small country, has become a threat and is amassing an army of soldiers, robots, and alien mutants. Bassad has allied himself with an unknown alien entity for his bid to world domination. Ray Poward (returning from Contra: Hard Corps) is deployed to thwart Bassad's scheme along with three of the newest members of the Hard Corps team: Tasha, a female mercenary; CD-288, a robot; and Bubba, an alien. After making the way to Bassad's Mountain Stronghold, the team defeats him in his armored pod, but is dragged into his mind for a final battle. With Bassad defeated, they are teleported to the alien entity, which turns out to be a small living planet. With it destroyed, the team is drifted in space, and a surviving small alien bug is seen hiding.
Each character plays exactly the same except for the type of weapons they wield and their movement speed. All characters start with a machine gun and flamethrower, but the remaining two slots are for character specific weaponry. The game plays from an isometric angle. Since the game takes place in three dimensions, enemies come from all angles. Ducking and strafing have been added to the player's abilities, as well as an auto-aiming feature to help attack airborne enemies. Jumping has been slightly changed as the characters no longer do tightly curled somersault jumps (a feature in every previous game since the arcade version of the original Contra). Unlike most of the other Contra games, where it takes one hit to defeat the player, this game gives the player a health meter. The player's progress can be saved to a memory card.
The game was first unveiled at the 1996 Electronic Entertainment Expo, during which Konami distributed 3-D glasses to attendees so that they could see the 3-D effect. This somewhat backfired, as journalists in attendance at the show reported that the 3-D feature was a "gimmick" and did not improve the game's visuals.
With the game 80% complete, Electronic Gaming Monthly reported that Randy Severin, senior product manager at Konami, was unhappy with the present state of the game, believing that some of the levels were too bright and colorful, and some of the bosses not menacing enough. The following month they received a near complete version which featured numerous adjustments to the color palette, speed, enemy AI, and graphics.
Like most 32-bit action games, Contra: Legacy of Waruses environments built of texture-mapped polygons