1996 June 23
Nintendo 64 released in Japan.

1996 August
The possibility of a Fire Emblem 64 was questioned in an interview with Shouzou Kaga (the creator of Fire Emblem), in the Super Tactics Book (a Genealogy of the Holy War guidebook). It is not explicitly stated that the next game will be on the Nintendo 64, only that it is intended to be a continuation of the Akaneia series of games.

Q) Is there a possibility of a new game? Assuming so, would it be on the Nintendo 64?

A) Although it's not been decided yet, if there is a next game, the level of strategy would be much higher and I would also return to something that's easier to play. I don't want to lose what makes Fire Emblem stand out from other games. As for the story, I'd like to explore Akaneia's world again, from before the start of Marth's adventures when he landed on Talis. Although enemies, I want to the develop the stories of interesting characters like Camus and Misheil.

1996 October
Fire Emblem 64 again questioned in an interview in the Genealogy of the Holy War Fan Special book.

Q) Will the next game be on the Nintendo 64?

A) I think being on the Super Famicom will be fine. If it were on the Nintendo 64, the battle scenes would use polygons and I'd have more to say.

1997 July 29
First confirmation of Fire Emblem 64's existence in an interview with Shigeru Miyamoto, in Japanese gaming magazine, Dengeki. Miyamoto confirmed that work has started on Fire Emblem 64, although it seemed to be in very early stages. (Source)

Question: What about Fire Emblem 64?

Miyamoto: We're earnestly producing Fire Emblem 64 (laughs). Actually, it'll probably come out after Mario RPG 2, the latter half of next year.

Question: What percent of it has been developed?

Miyamoto: The plans for Fire Emblem 64 are steadily progressing. The program team is completing Mario RPG 2, trying to come up with a playable demo... I wonder if I've said too much.

1997 September
BS Fire Emblem first broadcasted.

1998
Fire Emblem 64 officially announced in the September issue of Japanese gaming magazine, 64 Dream. It wasn't stated whether it would be released as a Nintendo 64 cartridge or a 64DD disk. (Source 1, Source 2)

1999 January
In an interview in the Fire Emblem Treasure book, Shouzou Kaga stated that work on a new Akaneia game ceased due to limitations with the Super Famicom. The next game was decided to be Thracia 776 instead.

Q) --Although I want to hear more about the new game... When were the new game's concepts first planned?

A) After Genealogy of the Holy War was completed, the theme of the next game was considered immediately. In fact, we had originally wanted to return to Akaneia, the stage of Mystery of the Emblem. However, although we intended on this direction from the very beginning, during the preliminary preparations, we realised it was too ambitious and difficult to do with the Super Famicom hardware... If possible, we'd like to do it for new hardware. [Goes on to discuss how they decided to start Thracia 776 instead]

Q) --Finally, including the new game, if in the future, Fire Emblem keeps advancing, what is your vision for the series?

A) As when we spoke previous, I would like to continue Akaneia's saga-- possibly a story related to Marth. Of course, we must wait until the proper environment comes. If the game can be made, to tell the truth, I'll have to think for a long time. I haven't actually thought much about it. Anyhow, if another game was made, I'd like to realise all of my designs.

1999 August 15
Shouzou Kaga left Intelligent Systems to form his own company, Tirnanog.

1999 September 1
Thracia 776 released.

2000 August
GameBoy Advance title Fire Emblem: Maiden of Darkness (Ankoku no Miko) appeared in the lineup for Nintendo's Space World event.

2000 September 22
In the November issue of 64 Dream, it was announced that Fire Emblem 64 was canceled because the hardware specs weren't suited to the game's system. Development was moved to Maiden of Darkness. (Source)

2001 July 26
Maiden of Darkness was renamed to Sword of Seals.

The rest is history.