Provided are a method and apparatus for establishing communication via a service provider providing a service of establishing communication between a transmitting terminal and a receiving terminal. The method includes receiving an encryption key from the service provider, transmitting the encryption key to an external device storing receiving terminal identification information required for establishing communication with the receiving terminal, receiving the encrypted receiving terminal identification information from the external device, and transmitting the encrypted receiving terminal identification information to the service provider.