Systems and methods are described for selectively transitioning execution environments in an on-demand code execution system based on a timing of a next request to execute code within such environments. The system can predict, from a history of requests to the system, when a next call to execute code in an environment, such as a virtual machine instance, will occur. The system can then calculate and compare the relative costs of maintaining the environment in an executing state or of halting the environment and moving the environment to a lower tier of memory, each of which can be based on the predicted next call to execute code within the environment. If the relative cost of maintaining the environment in an executing state exceeds that of halting the environment and moving the environment to a lower tier of memory, the virtual machine is halted and transitioned to secondary memory.