A public-key based secure messaging system with automatic receiver enrollment is disclosed. A sender in the system first determines whether a receiver has a public key. If the receiver has a public key, the messages will be sent to the receiver using a standard public-key based encryption. If the receiver does not have a public key, the first message will be sent to the receiver using a delivery method that does not require the receiver to have a pair of public and private keys prior to sending the message. However, when the receiver accesses the first message, a pair of public and private keys will be automatically generated at the receiver and the public key will be made available for encrypting subsequent messages sent to the receiver.