Trust is of paramount concern for tenants to deploy their security-sensitive services in the cloud. The integrity of virtual machines (VMs) in which these services are deployed needs to be ensured even in the presence of powerful adversaries with administrative access to the cloud. Traditional approaches for solving this challenge leverage trusted computing techniques, e.g., vTPM, or hardware CPU extensions, e.g., AMD SEV. But, they are vulnerable to powerful adversaries, or they provide only load time (not runtime) integrity measurements of VMs. We propose TRIGLAV, a protocol allowing tenants to establish and maintain trust in VM runtime integrity of software and its configuration. TRIGLAV is transparent to the VM configuration and setup. It performs an implicit attestation of VMs during a secure login and binds the VM integrity state with the secure connection. Our prototype’s evaluation shows that TRIGLAV is practical and incurs low performance overhead (≤ 6%).