The story begins with the arrival of a trio from Cypress, headed by Woldol, Cypress' ambassador. After Woldol uses a bolt spell to dispatch some guards, he and his cohorts make vague threats. They then offer Anri a gift, which, when opened, engulfs her in a black fog. Apparently Anri has been put under a sleep spell that only King Edmond of Cypress can lift.
Gardiana sends it's best soldiers (including Luke) to Cypress to kill Edmond (regicide = diplomacy), but a month after the army set sail, it's disappeared. It seems as if Gardiana will have to knuckle under to Cypress... Then Ruce appears with a force (that, save for Nick, consists of relatives of the original Shining Force), and explains that he and his friends, led by Nick, plan to defeat Cypress. Lowe will accompany the group as an advisor, and Ken will stay behind to handle things in Gardiana.
The group sets sail for Cypress... but soon runs into trouble. They're attacked by a Dark Mage, who, after being defeated, sets fire to the ship. Forced to abandon ship (and all of their supplies), the group swims to a nearby island. When everyone washes ashore on Miniyom, they encounter some Cypress soldiers harassing the locals. Naturally, the Force vanquishes the oppressors, and one of the locals joins the Force in support against Cypress. The Force then proceeds to Miniyom Bastion from which, with the help of Claude (who is part of the Cypress Resistance), they procure another ship.
With Claude leading the way, the Force sails to Asreet Island, the base of operations for the Cypress Resistance. By the time the Force arrives, Cypress is busy trying to smoke out the Resistance fighters. After beating back Cypress, Stock and Mayfair, also of the Resistance, join the Force. The Force continues on to Bazoo's Tower; since he's Woldol's right-hand man, he can probably be pumped for information. After defeating Bazoo, Yeesha joins the Force, and it is revealed that Nick is actually the Prince of Cypress, which casts some suspicion on him.
The Force continues sailing to Cypress, but the ship is stopped and searched by customs. After some Force members get by the inspection with bogus stories, King Edmond shows up, recognizes Nick, and demands that he be arrested. After a brief scuffle, Gyan, one of Nick's allies, shows up and explains the situation to the Force. Apparently Nick's father, the King of Cypress, was killed by Edmond or Woldol, and after Cypress was taken over by that duo Nick travelled to Gardiana to get help. Gyan joins the Force and sets them on a course toward Cypress' palace.
After making their way through the pampas, and the Death Tunnel (where you meet up with Kashing, who was in the army sent to Cypress in the beginning of the game), the Force arrives outside Gundoll fort. Dantom and Frabell are there to greet them. Though she does not face the Force directly, Frabell sends her soldiers. After she fails, the fight carries on into Gundoll fort, where the Force faces off against Dantom. Dantom doesn't really want to fight, but he's bound by honor to do battle for Cypress. When he is defeated, he warns the Force about Woldol, who he says worships an evil spirit called Iom.
Now that the Force has made it through Gundoll fort, they can proceed into Cypress. Edmond, though, meets them on the battlefield. Once beaten, Edmond calls Nick a traitor, believing Nick killed him to claim the throne. Once the Force has made it's way to the castle gates, they'll have to get by Geppel. Inside, Bazoo and Frabell will hold off the Force long enough for Woldol to summon Evil Monster. They'll then do battle with Woldol and Evil Monster.
With the monster beaten, Woldol starts to take off, but is stopped by Luke. Luke, brandishing the Sword of Hajya, explains that it can injure Iom, and that Woldol wanted to take over Cypress so he could obtain and destroy the sword. Woldol, who simply must have the sword, transforms himself into a giant scorpion thing, and attacks. During the battle, Woldol spits venom on Nicks right arm.
Once Woldol is finally defeated, Luke and his son, Ruce, have a cheerful reunion. While that is going on, Nick passes out as his arm, covered in vemon, turns to stone. Iom then makes his presence known, telling Nick that, in order for him to restore his arm, he'll have to face Iom sometime in the future.
With the villains defeated, the spell on Queen Anri is lifted. With Edmond vanquished, Nick now sits on Cypress' throne. Peace between the two countries is restored. Cypress makes plans to explore the interior of the continent, in search of Iom and his servants.