The events of Battlezone II: Combat Commander are set in an alternate version of the 1990s, in which access to alien technology necessitates the creation of an international peacekeeping force, the International Space Defense Force (ISDF), whose role is to oversee distribution of the rare bio-metal resource and mediate disputes between member nations.

After the initial introduction segment of the game, the player learns that an extraterrestrial fleet has gathered at the outskirts of the solar system. General Braddock, of the ISDF, orders the alien fleet destroyed. During the battles on Pluto and the soon-discovered Tenth Planet, called the "Dark Planet", it becomes apparent that the aliens, calling themselves the Scions, are in fact the remnants of a long-abandoned project to create super soldiers by merging bio-metal with human soldiers against their will. The player will play as Lieutenant John Cooke and will go on several missions under the command of Commander Shabayev on the Dark Planet.