The Lost Continent
The next destination is the “weird-looking structure” - the city of Esto Gaza which you may or may not have been to previously. Close to where the Blue Narciss docks though are some Chocobo Tracks. Wander around this area until you run into another Friendly Monster named Feather Circle.
You can take this opportunity to deliver another Kupo Nut to Mugato in Gizamaluke’s Grotto to receive another random item. This is part of the Kupo Nut side quest.
Lastly, take this opportunity to complete the Chocographs side quest and do all of the Chocograph hunting that is available at this point in the game if you have not already.
At this point in the game you will find that you are pretty hard up for healers. Eiko is now missing and Dagger continues to struggle with her ability to concentrate, causing random attacks and spells to fail in battle. Your best bet at this point is to add Quina into your party and to use Quina’s Blue Magic spell “White Wind” to heal the party.
Vivi also becomes extremely powerful at this point in the game due to some weapons he has and will get. The High Mage Staff or Gaia Gear can be used to teach him Osmose and he will soon receive a staff in Mount Gulug that will teach him his most powerful elemental attacks (specifically Firaga, Blizzaga and Thundaga). It is also recommended that you include him in your party.
Enter Esto Gaza and some cutscenes will take place inside the entrance. The Bishop will tell Zidane and his party that Kuja and the Black Mages passed through Esto Gaza and had Eiko with them. There are ton of new items available at the Esto Gaza Shop this time around including:
Make sure you have a fair number of Vaccines on you as well in preparation for the upcoming dungeon. There is also a hidden Wing Edge on the right side of the shop behind the counter. Exit Esto Gaza out the back going down the same pathway that Kuja and the Black Mages took.
Speak to Mogrika the moogle to pick up a letter from Artemecion to Mogrika. Speak to Mogrika again using the Mognet option to pick up a letter from him to Moolan. Save your game and then continue down the pathway.