The game stars Marth, the hero of Fire Emblem: Shadow Dragon and the original Mystery of the Emblem as he fights in a conflict known as the "War of Heroes". He is accompanied by his trusted friend, an Altean knight and hero of the war completely forgotten by history, referred to as the "Hero of Shadow".
Players can customize the unit, who's named Kris by default, including their appearance, class and growth rates. New prologue and sidequest chapters heavily feature your custom character and also offer opportunities to recruit previously unobtainable characters.
One of the extra features is that you can play a remake of Fire Emblem: Archanea Saga. Every character that only appeared in Fire Emblem: Shadow Dragon and the Blade of Light, Fire Emblem Archanea Saga, and/or Fire Emblem: Shadow Dragon returns in this installment.
- See main article: List of characters in Fire Emblem: New Mystery of the Emblem
Every Character, unlike in Shadow Dragon, can be recruited in the same playthrough without having to kill other units. As such, it is possible to have every character recruited and alive on one playthrough.
- See main article: List of chapters in Fire Emblem: New Mystery of the Emblem
Unlike the original, this skips Book 1. Every chapter's allowed unit limit has been increased by 1 to account for the Player's Character.
- See main article: List of Music in Fire Emblem: New Mystery of the Emblem
- This is the only Fire Emblem DS game to not be released overseas.
- The game utilizes the Wi-Fi Connection in a similar manner to Shadow Dragon.