Abstract Load balancer, as a key component in cloud computing, seeks to improve the performance of a distributed system by allocating workload amongst a set of cooperating hosts. A good balancing strategy would make the distributed system efficient and enhance user satisfaction. However, the balance of Host Machines (HMs) in a real cloud environment often breaks due to frequently occurred addition and removal of Virtual Machines (VMs). Therefore, it is essential to schedule the VMs to be reBalanced (VMrB). In this paper, we first summarize and analyze the existing studies on load rebalancing. We then propose a novel solution to the VMrB problem, namely a Pareto-based Multi-Objective VM reBalance solution (MOVMrB), which aims to simultaneously minimize the disequilibrium of both inter-HM and intra-HM loads. It is one of the first solutions that leverages the inter-HM and intra-HM loads and applies a multiple objective optimization strategy to overcome the virtual machine rebalance problem. In our work, we keep migration cost in mind and propose a hybrid VM live migration algorithm that significantly reduces the I/O complexity of VMrB processing. The proposed rebalancing solution is evaluated based on two synthetic datasets and two real-world datasets under a CloudSim framework. Our experimental results show that MOVMrB outperforms other existing multi-objective solutions and also demonstrate its extensibility to support complex scenarios in cloud computing.