Major Gooding was an officer in the Green army. On his final mission, Gooding was leading a squad (which included Sarge Hawk) through enemy territory in the real world. They reached their evac point, but were ambushed by Tan. Gooding was hit 3 times; the final bullet blowing off his right arm and knocking him into the kitchen sink drain. All of his squad, except Sarge, were killed in the ambush. After calling in an airstrike, Sarge found Gooding's severed arm, which led him to conclude Gooding was killed as well. Though Gooding weakly called out, Sarge could not hear him. Sarge boarded the Chopper, and ordered the pilot to leave the combat zone. In the aftermath, Major Gooding, angered at the thought that Sarge had abandoned him to die, renounced his previous loyalty to the Green. "...when the chopper took off that day, Major Gooding died, and Lord Malice was born." Eventually the Tan found him, and pieced him back together, giving him a mask and a mechanical arm.
Years later, at the news of General Plastro's intention to surrender to the Green, the vengeful Malice gathered Tan followers that didn't want peace between the Green Nation and Tan Republic; creating a new rogue faction. Grimm tasks Sarge with seeking out Malice, who has stolen Army Men infantry molds; meaning he is capable of creating an army. Sarge does not take Bravo Company with him, allowing them instead to attend a peace ceremony taking place in Greentown, where Plastro will surrender. When Sarge finds plans of a bomb to detonate at the ceremony, he is contacted by Malice, who tells him the fate of those in Greentown is in Sarge's hands. Malice detonates the bomb, killing both the Tan and Green, including all members of Bravo Company, except Sarge, who arrives too late to stop the tragedy. Sarge sets out on a mission to destroy Malice.
Sarge reaches Lord Malice's fortress, which has a portal leading to a kitchen Sarge recognizes as the place of the ambush. In the end, Sarge battles and fatally wounds Malice. Sarge asks why Malice killed the Green and Tan in Greentown. Malice reveals that it was simply to make Sarge suffer. Sarge removes Malice's mask only to be shocked to discover Malice was actually Major Gooding, who was accidentally left for dead. Sarge reflects over the death of Malice, "I tried to make sense of what happened, but the only clear thing that kept ripping through my skull was that war makes no sense." As Sarge leaves, a curtain falls off a collection of molds with the names of Grimm and the heroes printed upon them; suggesting Malice merely killed copies of those close to Sarge to play on his emotions.