Two countries, Temision and Halicarnassus, are at war with each other. King Ferdinand of Temision commands war magicians, hoping to gain the upper hand in the struggle thanks to their power. A girl named Leina was taken to the court of Temision when she was a child, and trained to become a prominent member of the team. However, as she completes another mission, she begins to have guilt feelings and questions the necessity to obey her superiors who order her to kill people. Very soon Leina begins to realize that even her love is jeopardized by politics and war.
Narsillion is a prequel to Leithian, telling the story that eventually led to the birth of Ellen, the heroine of the earlier game. Like Leithian, it is an action role-playing game taking place in vast interconnected environment consisting mostly of outdoor areas populated by enemies. The gameplay system is also similar to that of the previous game. The player controls a party of characters, manually fighting with the leader and assigning AI behavior (attacking, using abilities and items) to the rest of the team. Money gained from defeating enemies can be spent in towns on weapons, armor, accessories, and items.
Like in Leithian, accumulated experience does not result in leveling up. Instead, the player must find specific magic circles where he or she can freely distribute experience points to raise the heroes' attributes such as maximum HP and MP, attack and defense rating, etc.