Techniques for orchestrating and prioritizing the rebuild of storage object components in a hyper-converged infrastructure (HCI) deployment comprising a cluster of host systems are provided. In one set of embodiments, a computer system can identify a list of storage object components impacted by a maintenance event or failure of a host system in the cluster. The computer system can further determine a priority class for each storage object component in the list, where the determined priority class is based on a virtual machine (VM)-level priority class assigned to a VM to which the storage object component belongs. The computer system can then initiate rebuilds of the storage object components in the list on a per-VM and per-priority class basis, such that: (1) the rebuilds of storage object components belonging to the same VM are initiated consecutively, and (2) the rebuilds of storage object components with higher priority classes are initiated before the rebuilds of storage object components with lower priority classes.