Black Mage Village

Take the Blue Narciss to a beach on the southeastern tip of the Outter Continent. You’ll want to go around the sinkhole area to the Northernmost area. If you enter the wrong sinkhole you’ll get attacked by Antillons. Pick the sinkhole with no puffs of sand coming out of it. This should be the one furthest North and a question mark should appear above Zidane’s head.

After you enter you’ll end up trapped in Kuja’s Palace. Once you’ve got control of Zidane walk straight down the path. The Black Mages will send you to Kuja’s room. Then walk right. Kuja will send you on a quest to a place called Oeilvert on the Forgotten Continent. You’ll need to pick a party that can survive where you can’t use magic. I’d choose Amarant, Freya, and Quina. You’ll have to fight with the remaining members as well so make sure you leave both parties balanced. Kuja will teleport you to the cave the airship is in. You’ll need to go up the stairs and left all the way to board the ship. You’ll automatically fly to the continent but you’ll have to make your way to the city on your own. For instructions on how to get there refer to the Oeilvert section of this walkthrough.