Techniques for stateful connection optimization over stretched networks are disclosed. Such stretched networks may extend across both a data center and a cloud. In one embodiment, configuration changes are made to cloud layer 2 (L2) concentrators used by extended networks and a cloud router such that the L2 concentrators block packets with the cloud router's source MAC address and block address resolution protocol (ARP) requests for a gateway IP address from/to cloud networks that are part of the extended networks. Further, the cloud router is configured with the same gateway IP address as that of a default gateway router in the data center and responds to ARP requests for the gateway IP address with its own MAC address. In addition, specific prefix routes (e.g., /32 routes) for virtual computing instances on route optimized networks in the cloud are injected into the cloud router and propagating to a data center router.