The game begins with an attack on Greentown by the Tan Republic and Sarge battling through the war-torn city to save it. After the battle, Sarge Hawk is informed by Colonel Grimm that the Tan Army has surrendered and that there will be a peace ceremony later that night, but that a rogue Tan division led by Lord Malice has stolen some infantry molds and can now build an army. Sarge's mission is to find and terminate Malice.
Sarge arrives in the area (a beach) and battles his way to the Tan portal. There, he discovers plans indicating that Malice has placed a bomb at the peace ceremony. Sarge charges through the portal to stop the ceremony but he is too late - as the bomb goes off, his entire squad, as well as Plastro, Colonel Grimm, the Heroes and the Green and Tan armies are annihilated. After Vikki dies in Sarge's arms, he then sets out to kill Malice.
He battles his way through the remains of Greentown to another Tan portal. Upon proceeding through the portal he finds himself in Malice's artillery base. Sarge destroys all the artillery and discovers a plastic well mine that Malice is using to build his army. Sarge floods the mine making it nearly unusable. He then travels across the desert to Malice's castle. Malice is using the castle as a communication center for his air and ground forces, as well as a prison base for some of the Green army's finest men. Sarge penetrates the castle's defenses, frees the prisoners and destroys the communications tower. Discovering a passage from the castle to a kitchen in the real world, Sarge flashes back to a time when he was in a similar kitchen, in a squad led by Major Gooding. During the mission, Gooding was ambushed and wounded by Tan forces. Sarge attempts to find him only to see Gooding's arm near the sink, leading him to the conclusion that Gooding was dead. As Sarge calls for extraction, the flashback ends, and Sarge moves forth.
At the end of the game, Sarge finally reaches Lord Malice's headquarters, where he battles Malice. After defeating and fatally wounding Malice, Sarge asks Malice why he killed the Greens and Tans in Greentown. Malice reveals that it was simply to make Sarge suffer. Sarge removes Malice's facemask and discovers that Malice was actually Major Gooding, who was accidentally left for dead. Eventually the Tan found him and turned him into Lord Malice. At the end of the scene, Sarge is seen walking out, saying that war makes ultimately no sense.
The closing scene reveals storage tubes inscribed with the names of the deceased soldiers from the Greentown attack, hinting that Col. Grimm and the Heroes, along with Vikki, may not have died, and perhaps Malice had simply killed copies of them in order to play on Sarge's emotions.
The game was generally rated as average or below average. Improvements on previous games included a new lock on feature as well as the ability to blow off enemy limbs. Most reviews also said that the darker appearance was nice. Drawbacks included sub-par graphics, repetitive gameplay and poor enemy AI.