Lucrecia's Cave - FF7 Walkthrough

Lucrecia's Cave is found in the central part of the large western continent and can be accessed after you acquire the Highwind and can begin the Chocobo Breeding Side Quest. The alternative way here is by using the submarine and traveling through an underwater tunnel to the north of Lucrecia's Cave, this location is shown on my map below.

Unless you have completed the Vincent Character Unlock Side Quest and have Vincent in your party you won't be able to enter this cave. The only reason for coming to this cave anyway is to get Vincen't Ultimate Weapon and his Level 4 Limit Break.

If Vincent is in your party, you'll be allowed to enter the cave and you'll witness a scene, after which you'll be put back on the World Map. Lucrecia won't speak to you again until you've fought a total of 10 battles, it doesn't matter where you fight them at but return to this cave when you do and Lucrecia will speak with you again.

This time she will reward you with Vincen't Ultimate Weapon Death Penalty and Vincent's Level 4 Limit Break Chaos.