To improve resource utilization and energy efficiency, cloud data centers use virtual machine (VM) consolidation to consolidate VMs to fewer physical machines (PMs) through live VM migration. However, improper VM placement may cause frequent VM migrations and constant on–off switching of PMs, which results in lower service quality and increased energy consumption. In this paper, we address this problem by proposing an effective and efficient VM consolidation approach called EQ-VMC, which has the goal of optimizing energy efficiency and service quality. In our approach, a discrete differential evolution algorithm is developed to search for the global optimum solution for VM placement. By integrating this solution with a set of algorithms proposed for effective host overload detection, VM selection, and under-loaded host detection, EQ-VMC effectively reduces energy consumption and improves quality of service (QoS). Extensive simulation demonstrates its effectiveness and shows its superiority to previous VM consolidation methods.