A method of establishing connection between a first mobile station (MS) and a second MS in a mobile communication system is disclosed. More specifically, the method includes transmitting to at least one base station (BS) a service message which includes information of at least one service type supported by the first MS and the second MS. Here the at least one service type relates to a multimedia service supported by each of the first MS and the second MS. Furthermore, the method includes transmitting a request message which includes information of at least one service type selected by the first MS, receiving a response message which includes information of the selected service type which is supported by both the first MS and a second MS, and transmitting a connection complete message between the first MS and the second MS for communication using the selected service type.