The present disclosure relates to a distributed disk image deployment during virtual machine instance creation, and to deploying a virtual machine instances based on disk image locality. On example method includes receiving a request to create a virtual machine instance identifying a disk image; determining one or more storage devices storing the disk image; determining a distance measurement between each of a plurality of computing nodes and the one or more storage devices storing the disk image; selecting a computing node on which to create the virtual machine instance based on a locality of the computing node to a storage device from the one or more storage devices storing the disk image, the locality including the distance measurement between the computing node and the storage device; and creating the virtual machine instance on the computing node using the disk image from the storage device.