From StrategyWiki, the free strategy guide and walkthrough wiki

The Cavern of the Stolen Fayth is an optional area you can visit either while on your way to Zanarkand, or when you get free reign of the airship. It is located after the northeastern exit of the Calm Lands, cross the bridge and then turn right and head down into the valley. There you'll find a Save Sphere, so save your game (as there's a boss fight coming up soonish). Now, we enter the Cavern of the Stolen Fayth.

[edit] The Cavern of the Stolen Fayth

When you first enter, there isn't any other paths, so just continue forward until you reach a fork in the road. Choose the fork to the right, when you'll see a dead end and a chest that has the item Megalixir in it. Continue forwards until you reach a room where you get a short cutscene, and then just continue onwards until you get to the crossroads. Choose the right path, to reach a room with a chest containing a Lvl. 2 Key Sphere, return to the junction, and head left.

You will soon reach another crossroads, continue forwards if you want to reach a chest containing a hard-to-get Fortune Sphere. Return to the fork you just left again, and again head left.

For one last time, you reach a crossroads. Head left for the Al Bhed Primer XXV, head right to reach the Save Sphere (highly recommended that you save here), and head north for two Mega-Potions. Continue east to reach a boss battle against Yojimbo.

[edit] Boss: Yojimbo

(todo: put this into a boss template or something - too lazy at the moment to do it myself) Yojimbo has 35,000 HP and is pretty nimble (he can evade attacks quite well). Yojimbo's dog will attack you (Daigoro) for a nominal amount of damage (300 tops), and Yojimbo himself will attack you for a bit more (Kozuka does about 500 damage to everyone and inflicts Poison). The trick here is to take him down before his Overdrive bar reaches its limit, as his Overdrive is devastating - Wakizashi does a lot of damage indeed. Defeat him using overdrives and regular attacks, or if you feel like it, treat this as an Aeon battle and bring out Yuna - Shiva or Bahamut are both good enough to tear down Yojimbo.

[edit] Further Exploration & Bargaining with Yojimbo

Stand upon the glowing pedestal and face the right. Press 'X' to teleport to a room that has two chests - one with an MP Sphere and the other with an X-Potion and the room on the left of the teleportation device has a chest with a weapon, the Flexible Arm, which can only be used by Rikku.

Take the teleport forwards to reach the Chamber of the Fayth. One wonders what Yojimbo does with the money he extorts out of summoners, as that's how he operates - he demands money. The more money you give him, the more likely he is going to use a good move. He thus has no useable Overdrive, unless you get him to really like you (ie, by giving him money to make a move), both of which increase his chances of using his better attacks, namely Wakizashi and the infamous Zanmato which instantly kills every enemy 100% of the time and even works on the likes of the Dark Aeons, Penance and the Monster Arena creations.

In order to gain Yojimbo into your small army of summonable monsters, you have to pay a lump sum to get him to join you. To minimise this cost, follow these instructions: When asked what you want, answer 'to defeat the greatest of enemies'. Yojimbo will then offer a sum. If you pay that amount, he'll join you. Better still, though, is to offer half that number plus one gil. Next, offer half the sum he then offers you plus one. This is as low as he will go - try to haggle any farther, he'll kick you out of the place.