A method and apparatus for establishing a Peer-to-Peer (P2P) connection between Mobile Stations (MSs) in a wireless communication system are provided. A method of operating a transmitting MS for establishing the P2P connection between the MSs in the wireless communication system includes when a location of a receiving MS is not known, requesting a Base Station (BS) to transmit a message instructing MSs to prepare for P2P setup, and thereafter, broadcasting to neighbor MSs a message requesting P2P-related information, receiving the P2P-related information from each of the neighbor MSs, generating a list of MSs capable of P2P communication using the received P2P-related information, and establishing a P2P connection by selecting the receiving MS from the list of MSs with which P2P communication is desired. Accordingly, in an environment where the location of the receiving MS is not known, the receiving MS can be found and thus the P2P connection can be established. Therefore, subscribers of P2P communication can be easily managed by the BS.