1. A computer-implemented method comprising: receiving a request to migrate a virtual machine instance from a first physical host computing device to a second physical host computing device; obtaining a history of resource use associated with the virtual machine instance; identifying an anticipated future pattern of resource use associated with the virtual machine instance based at least partly on the history of resource usage; determining, for each of a set of potential future migration times distinct from a present point in time, an estimated length of time for migration of the virtual machine if migrated during the potential future migration time, wherein each estimated length of time for migration is determined based at least in part on the anticipated future pattern of resource use associated with the virtual machine; selecting a migration time from the set of potential future migration times based at least in part on the estimated length of time for migration of the virtual machine if migrated at the selected migration time; and causing the virtual machine instance to be migrated at the selected migration time.