The scenario takes place quite some time after the first one. King Jayanegara has succeeded his father, Raden Wijaya (the king and founder of the Majapahit Empire, from the first scenario), to the throne, but rebels under the lead of court official Rakrian Kutri hold him captive in the city of Trowulan and plan to execute him. Gajah Mada, head of the royal guard and eponymous protagonist of the campaign, has to free his king from the city with help from prime minister Arya Tadah, before Kuti can fulfill his plan.