Connectivity between data centers in a hybrid cloud system having a first data center managed by a first organization and a second data center managed by a second organization, the first organization being a tenant in the second data center, is optimized. According to the described technique, a path-optimized connection is established through a wide area network (WAN) between a first gateway of a first data center and a second gateway of a second data center for an application executing in the first data center based on performance of paths across a set of Internet Protocol (IP) flows. Application packets received from the application at the first gateway are forwarded to a WAN optimization appliance in the first data center. WAN optimized application packets received from the WAN optimization appliance at the first gateway are then sent to the second gateway over the path-optimized connection.