In a Converged IP Messaging (CPM) service, an arbitrary terminal generates a message based on a user input, and transmits the message to a CPM server. Upon receiving the message, the CPM server requests a presence server to provide presence information corresponding to a recipient of the message. The presence server searches for presence information corresponding to the recipient in response to the request of the CPM server, and transmits the searched presence information to the CPM server. Based on the transmitted presence information, the CPM server decides to perform interworking for the message, decides a type of a messaging service for interworking, and transmits the message to an Interworking Function (IWF) according to the decided type of the messaging service. The IWF receives the message, converts the message according to the decided messaging service, and transmits the converted message to the recipient.