The story of New Mystery of the Emblem remains from the original version. The game is set on the continent of Archanea, a land also featured in the first Fire Emblem title Fire Emblem: Shadow Dragon and the Blade of Light. In Shadow Dragon and the Blade of Light, the land was threatened by the dark sorcerer Gharnef, who summoned the dark dragon Medeus into the world. After becoming a fugitive from his kingdom after an attack on his kingdom, Archanean prince Marth went on a quest to reclaim his kingdom and defeat Gharnef and Medeus. By the events of New Mystery of the Emblem, Marth's old ally Hardin has ascended the throne, but begins expanding the military and dominating the other regions of Archanea. Marth investigates, and discovers that both Gharnef and Medeus are still alive, and Hardin has been corrupted by them.
A new sub-plot introduced in New Mystery of the Emblem involves the inclusion of the Avatar and a group of assassins sent by Gharnef to kill Marth and his allies. The assassins initially send a spy named Katarina to infiltrate Altea as a new recruit, where she befriends the Avatar and the other members of her squad before revealing her true purpose and launching an attack on Marth. The recruits prevent the attack while Katarina escapes, and the Avatar is appointed as Marth's personal bodyguard to protect him from future assassinations and accompanies him during the war against Archanea as "The Hero of Shadow".
