A distributed key management system (KMS) includes a central KMS server and multiple intermediate KMS servers. The central KMS server replicates managed keys to the intermediate KMS servers. An intermediate KMS server receives a KMS service request from a KMS client, where any of the intermediate KMS servers are capable of servicing the request. The intermediate KMS server performs the action requested if it has access to the necessary managed key and returns the response to the KMS client. If it does not have access to the necessary managed key, the intermediate KMS server transmits a request for the managed key to the central KMS server. The intermediate KMS server receives the managed key, performs the action requested, and returns the response to the KMS client.