Various techniques and procedures related to encryption key versioning and rotation in a multi-tenant environment are presented here. One approach employs a computer-implemented method of managing encrypted data and their associated encryption keys. In accordance with this approach, a key splitting process securely stores a master key used to encrypt tenant-level encryption keys, a key versioning process is used to securely track updated encryption keys, and a key rotation process is used to rotate encrypted data to an updated version of a tenant-level encryption key.