Methods and apparatus for instance migration to support rapid recovery from correlated failures are described. A failure event affecting one or more compute instances of a provider network, including a particular compute instance hosted at a first instance host, is detected based on an analysis of health status information. A determination is made as to whether a particular compute instance meets an acceptance criterion for a failure-induced migration. The acceptance criterion may be based on storage-related requests from the particular compute instance. If the particular compute instance meets the acceptance criterion, one or more configuration operations are initiated to re-launch the particular compute instance at a different instance host.