A unified messaging system is configured for encrypting messages. The calling party is prompted to encrypt the unified message, for example as part of an extended options menu. The unified messaging system encrypts the unified message based on an encryption key input by the user into an encrypted message, and generates an open-network destination header for identifying a destination location for the encrypted message according to an open-network protocol. The unified messaging system then outputs the open-network destination header and the encrypted message as an open-network encrypted message to an open-network message store. During retrieval of the message, the unified messaging system identifies the encrypted message and prompts the destination subscriber for a decryption key; the unified messaging system performs a decryption operation to recover a decrypted file, and outputs the decrypted file for playback to the user.