A vendor of virtual machine images accesses a virtual computer system service to upload a digitally signed virtual machine image to a data store usable by customers of the virtual computer system service to select an image for creating a virtual machine instance. If a digital certificate is uploaded along with the virtual machine image, the virtual computer system service may determine whether the digital certificate has been trusted for use. If the digital certificate has been trusted for use, the virtual computer system service may use a public cryptographic key to decrypt a hash signature included with the image to obtain a first hash value. The service may additionally apply a hash function to the image itself to obtain a second hash value. If the two hash values match, then the virtual machine image may be deemed to be authentic.