Studies have shown that overlay networks can significantly improve network performance; and with their large global footprint and flexible virtual machines offering, cloud service providers offer the new unique capability for users to easily and quickly create their own overlay networks. However, can an overlay network, built on a cloud service provider infrastructure, actually improve network performance, and if so by how much? These questions are critical given that existing studies have relied on high-speed experimental aca- demic networks, but similar available opportunities for per- formance improvement have not been established in the pub- lic Internet. As such, to answer these questions, we deploy an overlay on top of the IBM Softlayer infrastructure, and conduct a number of measurements using multiple clients situated across the world. In contrast to previous studies, we observe that simple forwarding frequently does not improve performance by much, and provides at best 13% improve- ment on average. However, we show that a TCP overlay, can provide up to 184% improvement in bandwidth for down- loads, and 228% improvement for uploads. Also, we find that in our cloud overlay network, the limiting bottleneck in network performance is actually not the overlay itself, but the Internet path to get to the overlay. These results have direct implications on the overlay design. More specifically, multi-hop indirection does not provide further improvement to single-hop indirection.