Software systems based on a service-oriented architecture (SOA) are partitioned into loosely coupled services. Services may be developed by different parties, deployed to different nodes and operated by different organizations. In an SOA services may evolve independently from one another, ideally without sacrificing interoperability. Supporting service evolution is still a topic of ongoing research. We present a versioning model for supporting the evolution of service-oriented architectures. We present suggestions for release management, evolution scenarios, and a versioning scheme for enterprise services. The presented approach has been developed for an SOA in the banking domain.