Techniques for stateful connection optimization over stretched networks are disclosed. In one embodiment, traffic of virtual machines (VMs) that are live-migrated from a data center to a cloud is temporarily tromboned back to the data center to preserve active sessions. In such a case, a stretched network is created that includes a network in the data center and two stub networks in the cloud, one of which is route optimized such that traffic does not trombone back to the data center and the other which is not so optimized. A VM that is live migrated to the cloud is first attached to the unoptimized network so that traffic tromboning occurs. Thereafter, when the VM is powered off (e.g., during a reboot), in a maintenance mode, or in a quiet period, the VM is switched to the route optimized network.