此游戏的故事舞台架构在前作“罗特帝亚王国”隔海旁的“马拉大陆”上，以及在远古时代中，曾有著具备著高文明的古代人建构了能漂浮在空中的要塞堡垒“黄金城”。 故事主角则为由前作人物罗特帝亚王子“雷特”，击败邪神的大战后所扶养的男孩“索尔”。在索尔成年后，原先以为非正统王室血统的他并不会继承罗特帝亚的王位，但因雷特器重索尔的英武而执意要将王位继承给他。得知必须负起王位的责任而闷闷不乐的索尔，便与儿时玩伴的王国骑士“亚雷斯”一同到外头散心。 之后在王城外的索尔及亚雷斯，遇到一名失去记忆的神秘少女“悠妮”。而索尔一行人从悠妮的言行中便猜测她应是来自于隔海的马拉大陆，便决定发起将悠妮护送回马拉大陆的冒险旅程。但索尔却殊不知，悠妮的来历与传说的黄金城有著密切的关联。