Although Instant Messaging (IM) services are now relatively long-standing and very popular as an instant way of communication over the internet, they have received little attention from the security research community. Despite important differences distinguishing IM from other internet applications, very few protocols have been designed to address the unique security issues of IM. In light of threats to existing IM networks, the authors present the Instant Messaging Key Exchange (IMKE) protocol as a step towards secure IM. A discussion of IM threat model assumptions and an analysis of IMKE relative to this using BAN-like logic are also provided. Based on their implementation of IMKE using the Jabber protocol, they provide insights on how IMKE may be integrated with popular IM protocols.