The prologue mission takes place during the Lightning Wars between the Solar Empire and the Iron Legion in Old Xylvania. The Iron Legion is on the verge of victory until a lone Imperial grunt uses the Staff of Qa-Len that activates an orbital beam, covering the Legion in rubble.
200 years later, Commander Pierce and Colonel Windsor of the Anglo Isles launch a surprise attack on the Solar Empire, believing they have created a super weapon. After a series of battles, the Anglos are repelled and Admiral A-Qira of the Solar Empire launches a counter invasion whilst creating an alliance with Marshal Nova.
Back at the Western Frontier base, Herman has a flashback to thirty years ago, when Tsar Gorgi launched a similar invasion on the Western Frontier, believing they harbor a super weapon. However, the Western Frontier defeated the Tundran Territories and forced Tsar Gorgi to sign a peace treaty. During that war, Herman's army discovered Xylvanians using mining equipment, but they were unable to figure out what they were looking for. The Anglo Isles successfully repels A-Qira's army, while A-Qira, frustrated by this defeat, drinks something, only to discover that it has poison in it, killing him.
Kaiser Vlad, who poisoned A-Qira, is revealed to be the one who orchestrated the war. Kaiser Vlad invades a preoccupied Tundra and brings back Kommandant Ubel from a POW camp. Another flashback campaign reveals how the Iron Legion was on the verge of victory over the Solar Empire until the use of Qa-Len's staff defeated them.
In the final campaign, the player takes control of the Tundran Territories' forces in an attempt to repel Vlad's expedition for the staff. Vlad finds the staff through the use of a large mechanized mining walker called the Mining Spider. But the Mining Spider is destroyed by the Alliance of Nations. Vlad is able to activate the staff, forcing the Alliance to pull out. Though having used the staff, Vlad buries himself with Kommandant Ubel in a cave. While Ubel digs them out, Kaiser Vlad holds the match and still persists that Xylvania's destiny of world domination burns brightly.