- NOT MISSABLE -
Vincent can be recruited during the party’s first visit to Nibelheim (and afterwards at any time), not the past/flashback versions with Cloud though!
Enter the mansion and go to the NORTH-WEST room where you can find a safe. When you try to open it you only have twenty seconds to input the combination (a countdown starts at the top-left corner).
The
combination is:
right to 36, left to 10, right to 59, right to 97. Upon inputting the correct code, the safe opens, revealing a mini-boss called Lost Number.
Defeat it and receive the Odin Materia and the Cosmo Memory Limit Break manual (Red XIII's ultimate Limit Break LV4).
Inspecting the safe a second time will yield you a Basement Key. Take this Basement Key to the basement (enter through the NORTH-EAST hidden entrance) and halfway through the hallway, open the locked door. Approach the coffin in the middle of the room and speak to Vincent. Continue the conversation, tell him about Sephiroth, ask him who he is,
and when you leave the room and re-enter the hallway, he will approach Cloud and join the party.Hope this helps!
Let me know if I need to adjust the solution.