The events of the game intersect with those of Suikoden II, but are more of a side story, hence the name gaiden.

Nash Latkje, the protagonist controlled by the player and an agent of Holy Harmonia's Southern Border Defence Force, has been assigned to obtain information to either verify or disprove a rumour concerning the appearance of one of the 27 True Runes in the Jowston City States.

During his travels, he encounters Sierra Mikain, a female vampire, who decides to accompany him on his journey.

After the completion of the Dunan Unification Wars (the events of Suikoden II), Nash intends to return to the capital of Holy Harmonia, the Crystal Valley.

His journey involves traveling through the Grasslands, where one village happens to be celebrating the legend of the Flame Champion and the Fire Bringers who stopped the Harmonians from invading some sixty years ago; an unfortunate stop over in Caleria, the base of operations for mercenaries of Southern Harmonian Border Defence Force; helping stop a wild dragon from terrorizing a village before finally reaching his destination.