Secure instant messaging is described. In an embodiment, a messaging device encrypts a challenge identifier to generate an encrypted challenge message, and communicates the encrypted challenge message via a peer-to-peer communication link to a recipient messaging device. The recipient messaging device decrypts the encrypted challenge message and encrypts the challenge identifier as a return challenge identifier to generate an encrypted challenge return. The messaging device receives the encrypted challenge return from the recipient messaging device, decrypts the encrypted challenge return, and verifies that the return challenge identifier matches the challenge identifier to establish that communications are secure when communicated via the peer-to-peer communication link and, optionally, to establish control policies pertaining to a communication received at the recipient messaging device.