An efficient option for reducing energy consumption in Cloud environments is consolidating the virtual machines (VMs) in minimum numbers of physical machines (PMs) and switching the unused hosts off. Over the past few years, there have been several attempts for VM consolidation heuristics. Unfortunately, most of the proposed works did not take into consideration the energy cost of PM power state transitions. In fact, the energy overhead created by transitions in and out of the low-power mode added to the overhead created by VM migrations might be too costly especially if the saved power, gained by consolidating VMs, does not compensate for this overhead. This paper focuses on the problem of VMs consolidation with regards to the energy cost of power state transitions, and suggests a new energy aware scheduling algorithm that operates as initial placement scheduler and VMs consolidation algorithm. The performance of our scheduler is evaluated using real workload traces and compared with three other schedulers.