The hideous Red Falcon, thought to have been destroyed long ago by the Earth's greatest commandos, Mad Dog and Scorpion, has risen again, this time very angry and thirsty for revenge. His armies are marching through the cities, across the lands, with the intention of exterminating the human race like a bad case of fleas. Two commandos, Jimbo and Sully, have come forth now to defeat Red Falcon and save what remains of the world from his hideous plans.

The Alien War is the third entry in the Contra series. Like its predecessors, it is a predominantly side-scrolling shooter with a heavy emphasis on action. The protagonist can carry two weapons (as opposed to one in the previous entries), and fire in eight directions when standing still. New abilities include climbing on walls, grabbing poles and navigating tanks. Parts of scenery can be destroyed.

In a few instances the protagonist will also participate in motorcycle changes. Two stages have a top-down view and are played differently than the side-scrolling levels, with more freedom of exploration and the necessity to complete mission objectives rather than simply advance in one direction and kill all the enemies.