Vincent Valentine

Go to the Shinra Mansion in Nibelheim. Once entered, check the letter on the left corner of the room. Go upstairs, on the left. Enter in the room on the right of Cloud. In the room there is a safe. Check it and choose the first option. You now must insert the combination within 20 seconds. Confirm every number by pressing the circle button. You have only one chance per number. The combination is: 36 right, 10 left, 59 right, 97 right. If you surpass any number you can't go back (you'll have to begin again). Once you've opened the safe, you'll have to fight the boss Lost Number
Defeat him (attack red parts with physical attacks and purple parts with magics). Once done, take the Odin Summon Materia, Red's 4° level limit (Cosmo memory) and the Key to the Basement. Go on the left and open the door on the corner of the room. Go downstairs and walk until the second screen (the one before the library). Check the coffin and speak with Vincent. Tell him about Sephiroth. Keep talking with him until he says to leave him alone. Go out and return to the spiral stairs: Vincent will join the party.

Yuffie Kisaragi

Go in the forest near Gongaga Town, in the world map. Walk around to provoke casual encounters. After a while, you should find Yuffie. Defeat her. You now are in a new screen. Ignore the Save Point (or Yuffie will steal your money and flee!). Do not even enter the menu. Talk with Yuffie and choose the following answers:

• Not interested.
• …petrified.
• Wait a second.
• That's right.
• …let's hurry on.

Yuffie will join the party.