This paper studies a security enhancement of instant messaging service. After the requirements and the assumptions are addressed, a modified Diffie-Hellman protocol suitable to instant messaging is presented. The main feature of the proposed protocol is to prevent malicious administrator from intercepting plain message and applying data mining techniques to obtain privacy of end users. From the viewpoint of communication and computational costs, the proposed protocol are evaluated and the comparison of some existing protocols is given. In addition, a trial implementation of secure instant messaging system is demonstrated.