Techniques for optimizing cluster-wide operations in a hyper-converged infrastructure (HCI) deployment are provided. In one set of embodiments, a computer system can receive a request to initiate a cluster-wide operation on a cluster of the HCI deployment, where the cluster includes a plurality of host systems, and where the cluster-wide operation involves a host-by-host evacuation of virtual machines (VMs) and storage components from the plurality of host systems. The computer system can further generate a set of recommendations for executing the host-by-host evacuation in a manner that minimizes the total amount of time needed to complete the cluster-wide operation. The computer system can then execute the host-by-host evacuation in accordance with the set of recommendations.