Vincent
WARNING: This page contains SPOILERS for Final Fantasy VII.
After finishing the events in Cosmo Canyon, you will be able to enter Nibelheim (for real, this time). This is the first chance you will have to get Vincent, and you can get him at any time later in the game. This includes times when Cloud is not leading the party.
Remember the Shinra Mansion that you saw in the Kalm Flashback? Well, that's where you need to go. Enter the front of the Mansion, take the stairs to the upper level, and head to the left. Enter the top room in this area. You'll see a safe there. The first step to getting Vincent is to open this safe. You can find out the numbers for the combination by using Hojo's notes in the bottom-left corner by the mansion's entrance. Or, I could just tell you. (Right 36, Left 10, Right 59, Right 97)
Go right to 36 and press confirm. Go left to 10 and press confirm. Go right to 59 and press confirm. Go right again to 97 and press confirm. If you pass any of the numbers, you must start over. For example, if you go to 37 right off the bat, you’ll have to start over. If you go to 36, then go left to 9, you’ll have to start over. And so on. There is no penalty for starting over, it's just frustrating.
Once the safe is opened, you'll be forced to fight Lost Number.
Lost Number: This thing can be tough as hell in a low-level game, and it can still be a pain in the ass even if you’re fairly well-leveled. You’re better off using only magic-based attacks at first. When you see half of the monster disappear, switch to physical attacks. (After half of it disappears, its defense to either magic or physical attacks will skyrocket, depending on what you used to kill the first half.) You can also Stop the thing using Cross-Slash, Seal Evil, Choco/Mog, or just plain old Stop. He’s more or less helpless once you stop him. If you need some quick physical damage, use Throw. People tend to underestimate the sheer destructive powers of Throw.
After the battle, grab the Odin Materia off of the ground, and grab the key to the basement from inside the safe. Now exit this area and head right across the hall. Enter the lower room and use your Select Button to see the hidden door. Go down it. Exit the first screen at the bottom. On the next screen, there is a wooden door at the top. Enter this door and press Circle next to the center coffin. Choose to “Talk about Sephiroth.” Press Circle next to the coffin a second time. This time, ask “Who are you?” (I will call him Vincent throughout this guide.) Once the coffin closes again, exit the room and try to leave the basement. Vincent will join your party.