A network-based service for the management of cryptographic key, such as a key management service (“KMS”), provides a web service application programming interface (“API”). Cryptographic keys managed by the service may be stored in a one or more network-connected cryptographic devices such as network-connected hardware security modules (“HSM”). The key management service maintains metadata associated with the cryptographic keys. When a request is received by the key management service, the key management service uses an identifier provided with the request to identify metadata associated with a cryptographic key used to fulfill the request. The key management service uses the metadata to identify a cryptographic device containing the cryptographic key. The key management service generates a set of commands for fulfilling the request such that the commands are compatible with a protocol implemented by the identified cryptographic device, and the set of commands are sent to the identified cryptographic device.