When Eliwood reunited with his father on the Dread Isle, Elbert lived just long enough to inflict a severe but not fatal wound on Nergal, and to warn Eliwood that Nergal would be back and that Eliwood and his friends would have to be ready when he was. During the return journey, Nils and Ninian informed Eliwood that Nergal was somewhere far to the east, i.e. in Bern. They stopped at a fortress near Ostia to rendezvous with Uther and inform him of these new developments, whereupon Uther suggested that they make a detour to the Nabata Desert on the Missur Peninsula to seek the "Living Legend" before heading to Bern.

The Living Legend was none other than the Archsage Athos, one of the Eight Legends of the Scouring, who agreed to help Eliwood and his friends in unlocking the Divine Weapons to aid in combating Nergal. For this purpose, he said, it would be necessary to travel to the Shrine of Seals in Bern. His friends Pent, Louise, and Hawkeye agreed to aid Eliwood as well. Athos teleported the group to Pherae, where they spent the night before setting out for Bern.

Eliwood and his companions clashed with one of the Reed brothers near the Bern-Pherae border, while Pent and Louise sought out an audience with Queen Hellene of Bern to ask her about the location of the Shrine of Seals.

Hellene had problems of her own, however, which she required Eliwood to resolve before she would aid him in finding the Shrine of Seals. Zephiel's coming of age ceremony was fast approaching, but the Fire Emblem, a vital component to the ceremony, had been stolen. Eliwood's task, therefore, was to retrieve the Fire Emblem and return it to Hellene.

Searching for clues as to the Fire Emblem's whereabouts, Eliwood and his companions traveled to the royal castle of Bern and, finding it unguarded, sneaked in. They overheard Prince Zephiel playing with Princess Guinivere, and King Desmond talking to Sonia; the latter conversation confirmed that the Fire Emblem was hidden in the Black Fang's fortress. After nearly being spotted by Sonia, Eliwood fled the castle only to find Vaida harassing Nils and Ninian. Because Vaida was empowered by Nergal, Eliwood was unable to do more than fight her to a stalemate, but eventually she tired of the fight and retreated.

Lyn used her tracking skills to lead the group in pursuing Vaida high into the mountains, to the Black Fang fortress. They arrived in time to eavesdrop on Sonia's next assignment for Jaffar, one of the Four Fangs: to kill Prince Zephiel that night. Eliwood and company were spotted by the Black Fang, however, and some enchantment prevented them from leaving the fortress until they had fought their way through to the source of the enchantment. One of the leaders of the Black Fang had the Fire Emblem in his possession, which Eliwood took before fleeing to the manse where Zephiel and Hellene lived.

They arrived at the manse that night and succeeded in stopping the attempt on Zephiel's life. The next morning, Hellene rewarded Eliwood with a map to the Shrine of Seals.

When they arrived at the Shrine of Seals, they found the surviving Reed brother and the last remnants of the Black Fang guarding it. After Eliwood defeated them, Athos teleported to the Shrine and admitted that while he could have simply teleported everyone else directly to the Shrine as well, he needed proof that Eliwood would not be swayed by the immense power of the Divine Weapons, and that the journey through Bern was a test of Eliwood's strength and determination. They entered the shrine and encountered Bramimond the Enigma, and they convinced it to open the seals guarding the Divine Weapons.