The placement of virtual machines (VMs) on a cluster of hosts under multiple constraints, including administrative (security, regulations) resource-oriented (capacity, energy), and QoS-oriented (performance) is a highly complex task. We define a new high-availability property for a VM; when a VM is marked as k-resilient, as long as there are up to k host failures, it should be guaranteed that it can be relocated to a non-failed host without relocating other VMs. Together with Hardware Predictive Failure Analysis and live migration, which enable VMs to be evacuated from a host before it fails, this property allows the continuous running of VMs on the cluster despite host failures. The complexity of the constraints associated with k-resiliency, which are naturally expressed by Second Order logic statements, prevented their integration into the placement computation until now. We present a novel algorithm which enables this integration by transforming the k-resiliency constraints to rules consumable by a generic Constraint Programming engine, prove that it guarantees the required resiliency and describe the implementation. We provide some preliminary results and compare our high availability support with naive solutions. © 2011 IEEE.