Techniques for dynamic management of virtual machine environments are disclosed. For example, a technique for automatically managing a first set of virtual machines being hosted by a second set of physical machines comprises the following steps/operations. An alert is obtained that a service level agreement (SLA) pertaining to at least one application being hosted by at least one of the virtual machines in the first set of virtual machines is being violated. Upon obtaining the SLA violation alert, the technique obtains at least one performance measurement for at least a portion of the machines in at least one of the first set of virtual machines and the second set of physical machines, and a cost of migration for at least a portion of the virtual machines in the first set of virtual machines. Based on the obtained performance measurements and the obtained migration costs, an optimal migration policy is determined for moving the virtual machine hosting the at least one application to another physical machine.