Systems and processes are described for a message service with distributed key caching for server-side encryption. Message requests are received by message handlers of the message service that cache data encryption keys used to encrypt and decrypt messages that are stored to message containers in back end storage. A metadata service obtains the data encryption keys from a key management service, caches the keys locally, and sends the keys to the message handlers upon request, where the keys are cached, again. The key management service may generate the data encryption keys based on a master key (e.g., a client's master key). The message handlers may send both message data encrypted using the data encryption key and an encrypted copy of the data encryption key to be stored together in the data store.