This chapter describes the Spontaneous Virtual Network architecture SpoVNet that eases creation and deployment of service overlays. First, we derive requirements for supporting service overlays in todays Internet. For instance service overlays must work across heterogeneous networks and should be able to incorporate mobile and/or multi-homed users as well. Then we describe components of the SpoVNet architecture and how they relieve service overlay programmers from several complex tasks. Finally, we illustrate the application of the provided SpoVNet service interface by giving an example for creating a service overlay for streaming videos to a group of users.