Set sometime after the events of Sarge's Heroes, Sarge and Vikki must team up to destroy Plastro's new secret weapon.
Due to many discrepancies with the events of Sarge's Heroes, its sequel and Portal Runners, it is considered an alternate universe.
The player can choose between Sarge Hawk, or Vikki Grimm, who will receive several objectives by radio, such as recruiting fellow squad members, escaping from prison, and breaking into enemy installations. This game has more cartoonish and super-deformed appearance, compared to the realistic designs of Army Men: Operation Green.
After a mysterious object falls from the skies and is taken by the Tan Republic, Sarge and Vikki are sent to investigate. The main objectives of the game are; One, infiltrate area 41 to use the portal to the real world. Two, find and rescue Riff from tan troops in the real world. Three, find way outside through the bathtub. Four, find and rescue Scorch. Five, find access codes to capture the base in the garage then return to the plastic world. Six, reclaim captured base from the Tans. Seven, return to area 41 and stop General Plastro from using the alien ship.