Methods and apparatus for securing client-specified credentials at cryptographically-attested resources are described. An indication is obtained that resources deployed for execution of a compute instance of a multi-tenant computing service at an instance host of a provider network meet a client's security criteria. An encrypted representation of credentials to be used at the compute instance to implement operations on behalf of a client is received at the instance host. The credentials are extracted from the encrypted representation using a private key unique to the instance host, used for the operations, and then removed from the instance host without being saved in persistent memory.