Recovery of virtual machines when one or more hosts fail includes identifying virtual machines running on the remaining functioning hosts. Some of the identified powered on virtual machines are suspended in favor of restarting some of the failed virtual machines from the failed host(s). A subsequent round of identifying virtual machines for suspension and virtual machines for restarting is performed. Virtual machines for suspension and restarting may be identified based on their associated “recovery time objective” (RTO) values or their “maximum number of RTO violations” value.