Technologies related to quorum-based Virtual Machine (VM) security are generally described. In some examples, VM data, such as a VM payload or other VM data, may be quorum-encrypted, such that a quorum of decryption keys may be used to decrypt the data. Decryption keys may be distributed among multiple VMs, with different decryption keys provided to different VMs, so that single VMs may not decrypt the VM data without decryption keys held by other VMs. To decrypt its data, a VM may assemble a quorum of decryption keys by requesting decryption keys held by other operational VMs, and the VM may then decrypt its data using the assembled quorum of decryption keys. The VM may be prevented from decrypting its data without a sufficient quorum of other operational VMs.