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, we 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 these using BAN-like logic is also provided. Based on our implementation of IMKE using the Jabber protocol, we provide insights on how IMKE may be integrated with popular IM protocols.