The Cavern of the Stolen Fayth is an optional dungeon located between the Calm Lands and Mt. Gagazet. The path to the Cavern can be found beneath the second bridge from the Calm Lands.
Before going in the cave, investigate the path opposite the dungeon to find the Rusty Sword. It will be sticking out of the ground between two big rocks. You will need this item later in the game.
While exploring the Cavern of the Stolen Fayth, you may run into a Fiend called the Magic Urn. You can attack one of its five eyes on the urn for the chance to win a random item. If you choose wrong, all three members of your team will receive a massive attack. Make sure their HP is high enough to withstand the attack. You can always flee from battle instead of fighting.
Follow the path until you reach a fork in the road. A treasure chest containing a Megalixir is located to the east.
Return to the main path and continue forward. A cut scene will play out explaining why a Fayth is located in this dungeon. The next fork in the road has a Lv. 2 Key Sphere in a treasure chest to the east. Pick it up and continue further into the cave.
Eventually, you will reach yet another fork in the road. Continue along the path to the north to reach a dead end with a treasure chest. This treasure chest contains a Fortune Sphere.
Take the path to the west to go deeper into the cavern. You will come across a three-way intersection. The fork to the north will lead to a treasure chest with Mega Potion x2. The fork to the west will lead to the Al Bhed Primer vol. XXV.
After gathering the items, take the fork to the east to reach a save sphere. Heal and save up because a boss battle is right up ahead.
Boss Battle: Yojimbo
You must battle this Aeon using your own team. Of course, you could always summon your own Aeon to go head to head with Yojimbo. This Aeon has high physical defenses, so it’s best to use Magic attacks. Don’t even try getting an Overkill, your team will not earn any AP or items at the end of the battle.
After defeating Yojimbo, step on the teleport pad up ahead and press X while the arrow is pointing north to teleport to the chamber of the fayth. You will get three options. Choose “To defeat the most powerful of enemies.” He will then ask you to pay a price. You will need to negotiate a price in order to recruit Yojimbo. Try the following options:
If you offer three times the final amount (591,000), Yojimbo will give you two Teleport Spheres in addition to joining your party.
Unlike the other Aeons, you cannot select attacks for Yojimbo. Give him Gil and he will use a variety of attacks on his own. Obtain and power up Auron’s Celestial Weapon, Masamune, to increase Yojimbo’s damage limit beyond 9999.
After recruiting Yojimbo, step on the telport pad in the previous area again. This time face the west before pressing X. You will teleport to a secret area that contains the Flexible Armor weapon for Rikku. Go back to the teleport pad and travel east to another secret area. This room has two treasure chests containing an MP Sphere and X-Potion x2.