One embodiment of a system for provisioning a new virtual machine instance on a target host based on an image of the new virtual machine instance includes a local storage for storing images of virtual machine instances currently running on the target host and a virtual machine creator coupled to the local storage for constructing the image of the new virtual machine instance at least in part using the images of virtual machine instances currently running on the target host.