Techniques and technologies for migrating workloads between different VM instance types based on changes in resource utilization over a period of time. Selecting one VM instance type to host workloads can result in use of a VM instance type that is optimized for the workload during one timeframe of a period of time, but is over-provisioned or under-provisioned for the workload during another timeframe of a period of time. Accordingly, a service provider network may analyze historical utilization patterns of workloads over a period of time, and identify different VM instance types that are optimized for the workloads during different timeframes of the period of time. The service provider network may then cause the workloads to be migrated between the different VM instance types over the period of time such that the workloads are hosted on VM instances that are optimized for the current resource utilization of the workloads.