A first analysis based on at least a subset of collected health metrics of a monitored resource is performed at a health monitoring service. If the first analysis indicates that the probability that the monitored resource is in an unhealthy state is above a threshold, a mitigation action that includes directing at least some of the workload away from the monitored resource is implemented. In addition, a remediation analysis of the monitored resource is started to determine, using at least one additional health metric that was not examined in the first analysis, whether a longer-term remediation action is to be initiated.