Modern Internet applications are typically hosted in the public cloud, with multiple server instances running within geographically distributed datacenters. Thanks to the abundantly available bandwidth on wide-area links that interconnect these datacenters, it is conceivable that bandwidth-intensive applications may improve their performance by relaying their traffic through such an inter-datacenter network. However, there does not yet exist a cloud service that provides a turn-key solution to tap into such available bandwidth resources conveniently. In this paper, we design and implement Stemflow, a new system framework that provides Inter-Datacenter Overlay as a Service based on the software-defined networking principle. It offers an attractive foundation that helps an Internet application to transparently improve its scalability and performance by using inter-datacenter networks for its traffic. With Stemflow, all deployed server instances will construct an overlay atop an inter-datacenter network, and the routing decisions to relay application traffic are made by a centralized controller. The algorithms needed to make these decisions are customized to meet the needs of individual applications, and are cached within the data plane. We motivate and describe the design decisions, and present an extensive experimental evaluation in public cloud infrastructures, using two example applications as our case studies.