The present invention is directed to a system and method for providing the secure exchange of messages utilizing an existing unsecured messaging network such as the Internet. A messaging proxy is provided between a sender of a message and the unsecured messaging network. In sending a secure message, the messaging proxy contacts a key exchange server via an authenticated secure connection. The messaging proxy generates a key with which to encrypt the message. The key is sent via an authenticated secure connection to a messaging proxy of a recipient. If the sender receives an acknowledgement of the recipient receiving the key, the message is encrypted and sent via the unsecured messaging network. The recipient then uses the key to decrypt the message. Should the recipient not have a proxy in place to receive encrypted messages and a corresponding key exchange server, the message is sent unencrypted.