An invention is described for securely deploying a provable identity for virtual machines (VMs) in a dynamic environment. In an embodiment, a fabric controller instructs a VM host to create a VM and sends that VM a secret. The fabric controller sends that same secret (or a second secret, such as the private key of a public/private key pair) to the security token service along with an instruction to make an account for the VM. The VM presents proof that it possesses the secret to the security token service and in return receives a full token. When a client connects to the deployment, it receives the public key from the security token service, which it trusts, and the full token from the VM. It validates the full token with the public key to determine that the VM has the identity that it purports to have.