Embodiments of the present invention provide an approach for migrating virtual machines across network (e.g., WAN) separated data centers (e.g., storage clouds). Specifically, under embodiments of the present invention, a first storage system associated with a first data center is synchronized with a second storage system associated with a second data center via a storage system link. Then, a minimal state of a virtual machine is migrated from a first computer in the first data center to a second computer in the second data center via a WAN link. Using the minimal state, the virtual machine is stored in the second computer. Thereafter, the storage system link is terminated. In addition, as updated pages are received in memory of the first computer, they are migrated to the second computer via the WAN link. Once this migration is complete, the WAN link can be terminated. Therefore, embodiments of the present invention provide at least two forms of synchronization: computational synchronization and storage synchronization.