Resource provisioning in compute clouds often require an estimate of the capacity needs of Virtual Machines (VMs). The estimated VM size is the basis for allocating resources commensurate with workload demand. In contrast to the traditional practice of estimating the VM sizes individually, we propose a joint-VM sizing approach in which multiple VMs are consolidated and provisioned, based on an estimate of their aggregate capacity needs. This new approach exploits statistical multiplexing among the workload patterns of multiple VMs, i.e., the peaks and valleys in one workload pattern do not necessarily coincide with the others. Thus, the unused resources of a low utilized VM can be directed to the other co-located VMs with high utilization. Compared to individual VM based provisioning, joint-VM sizing and provisioning may lead to much higher resource utilization. This paper presents three design modules to enable the concept in practice. Specifically, a performance constraint describing the capacity need of a VM for achieving a certain level of application performance; an algorithm for estimating the size of jointly provisioning VMs; a VM selection method that seeks to find good VM combinations for being provisioned together. We showcase that the proposed three modules can be seamlessly plugged into existing applications such as resource provisioning, and providing resource guarantees for VMs. The proposed algorithms and applications are evaluated by monitoring data collected from about 16 thousand VMs in commercial data centers. These evaluations reveal more than 45% improvements in terms of the overall resource utilization. © 2010 ACM.