Aspects of the disclosure relate to dynamic crypto key management for mobility in a cloud environment. A computing platform may receive a request to generate a new tenant master key and a new server recovery key. Subsequently, the computing platform may send to a cloud-based key vault server, the new tenant master key and the new server recovery key. The computing platform may send to a tenant database, the encrypted server recovery key. As a result, the computing platform may provision the enrollment servers with the encrypted server recovery key. In some embodiments, the enrollment servers are configured to manage enrollment of policy-managed devices in a policy enforcement scheme and to authenticate with the key update service based on the encrypted server recovery key.