Fort, Elicia and Legna are childhood friends, all orphans who live at a village orphanage. The three form a love triangle, as both Fort and Legna love Elicia. Fort is known to be a genie, a human who can summon and control monsters. He is frequently bullied due to his genie status, and Legna often comes to his aid.
Fort's village is attacked and burned by the Empire, an expansionist government with a powerful military. Elicia is trapped inside the orphanage, and Fort runs to her rescue. When an Empire soldier takes Elicia captive, Fort's power activates and he summons monsters in desperation. The monsters kill the soldier but also attack Elicia. Legna arrives too late to save Elicia. Legna blames Fort for Elicia's death for the rest of his life.
Fort awakens in an Empire prison, and a shadowy creature appears, called Wicca. Wicca is a devil who makes contracts with monsters. Wicca promises to break Fort free, provided he learns to control his genie power. Fort agrees. From this point onwards, the player can build and customize a party of up to four members (including Fort). Fort escapes into the Forest of Black Poison, and reaches the Town of Fatma. Here he meets Evans, the leader of the resistance movement against the Empire. Evans requests Fort to deliver an important letter to the Village of Barbas. Fort delivers the letter and the response back.
Evans requests Fort to aid the resistance in freeing other genies held by the Empire. Fort enters the Genie's Camp but discovers it is a trap laid by Legna, now a pawn of the Empire. Legna is also a genie and the leader of the Empire genie troop. Legna summons powerful monsters to kill Fort. Evans uses a flash bomb to blind Legna, and they all escape in the confusion. Evans suggests gaining the support of the Kingdom, a small and defensive government often targeted by the Empire. Evans and Fort make a perilous journey to meet Queen Illia of the Kingdom. Queen Illia agrees to join the resistance if Fort liberates the Gallia Fortress, a stronghold of the Empire.
Fort and Evans manage to liberate the Fortress, but Queen Illia demands that Fort join her army, and refuses to join the movement. To force her hand, Evans sets fire to the Village of Barbas. Fort refuses to ahelpid Evans, so Evans attempts to assassinate Fort. Fort escapes and uses a secret path (the Abyss Cloister) to reach Queen Illia's castle. Evans gets to Queen Illia first, and blames Fort and the Empire for the burning. The Kingdom makes preparations for war with the Empire. When Fort arrives, Queen Illia attempts to kill him, but Wicca helps Fort escape via a secret passageway.
Almost freed, Fort is confronted by Legna once again, who is now an extremely powerful genie. Legna has staged a coup d'état against the Empire and become emperor. He has changed the imperial policies to be pro-genie and anti-human. The Kingdom is defeated and Queen Illia flees with a few guards. Legna imprisons Fort after he refuses to join the Empire. Evans agrees to help Fort break free if Fort rejoins him. Fort reluctantly agrees, and escapes the Zolda Prison. Fort rescues Queen Illia from the Town of Hide, where she is being held captive by the Empire. Queen Illia has lost her mind after severe torture. Evans asks Fort to enter the Empire castle and distract the genie troop. Fort activates an ancient flying machine and uses it to enter the castle from the air. Fort confronts and defeats various members of the genie troop.
Legna finally appears and refuses to change his anti-human policies. Fort and Legna battle using their monsters, and Fort defeats Legna. Legna dies choking on his own blood, and claims he was never a genie. He tells Fort that Elicia is still alive, and he became a genie using her blood. Legna confesses that he did everything he could to save Elicia, but failed. With Legna dead and the Queen insane, Evans takes the throne and is revealed to be a megalomaniac. Fort leaves to rescue Elicia. Fort enters deep into the Genie Production Factory, and finally encounters Elicia, now in a deep coma. With Wicca's help, Fort enters Elicia's unconscious field. Fort frees her mind by defeating her fears, which appear as a final monster. Fort and Elicia are reunited at last.