Embodiments disclosed include a method for establishing a communication connection. The method includes: receiving a connection request message transmitted by a first terminal, the connection request message carrying a first user identifier and a second user identifier; determining a second relay node corresponding to the second user identifier, the second relay node being a relay node communicatively connected to a second terminal; transmitting the connection request message to the second relay node through a relay path to the second relay node, so that the second relay node transmits the connection request message to the second terminal; and transmitting, in response to receiving a connection confirmation message returned by the second terminal, the connection confirmation message to the first terminal, so that the first terminal establishes a communication connection with the second terminal based on the connection confirmation message.