A method and apparatus for establishing a call between a calling mobile station and a called mobile station in a mobile communication system are provided. The method involves the steps of receiving a service request message from a calling radio network controller (RNC), and transmitting an incoming call request message to a called radio network controller (RNC), transmitting a first service connection path setup request to the calling RNC prior to receiving a service acceptance message from the called RNC, transmitting a second service connection path setup request to the called RNC, if the service acceptance message corresponding to the incoming call request is received from the called RNC and then if a first service connection path setup response corresponding to the first service connection path setup request is received from the calling RNC, and receiving, from the called RNC, a second connection path setup response corresponding to the second connection path setup request.