The game's format is similar to that of Bionic Commando, with an overhead map of the various stages. In order to progress, the player must navigate the map and clear each sub-stage leading up to one of several Cobra bases. Once in a base, the player must fight through hostile Cobra forces and also complete a secondary mission (such as rescuing hostages, setting bombs, or locating a key item). Each base stage concludes with a battle against a Cobra leader (Overkill, Cesspool, Firefly, Major Bludd, Destro, and Cobra Commander).
There are several playable characters in the game: General Hawk, Roadblock, Wet Suit, Snake Eyes, Storm Shadow, and Duke. At the beginning of the game, the player can only use Hawk, and must unlock the other characters one by one by completing other stages. Once players have discovered a character, they can "decide" which characters will come with them, and alternate between them during gameplay by pressing the “pause” button and accessing the pause menu. Each character has their own agility, stamina and strength rating.
In addition to the playable characters, Gung-Ho, Spirit, and Big Bear can be summoned to support the player by refilling life or weapon ammunition, though they must first be rescued by completing certain sub-stages. Stalker also appears but only in cutscenes, as he coordinates the mission from the G.I. Joe base.
Having survived the last time he fought the G.I. Joe Team, Cobra Commander has raised the ancient island of Atlantis from the ocean depths and is using it as a base. With a nearly indestructible army and powerful space weapons, the power-crazed Cobra is plotting to use the long lost powers of the Atlanteans in their bid to rule the world.