In an environment of constant change and variation driven by competition and innovation, a software service can rarely remain stable. Being able to manage and control the evolution of services is therefore an important goal for the Service-Oriented paradigm. This work extends existing and widely-adopted theories from software engineering, programming languages, service oriented computing and other related fields to provide the fundamental ingredients required to guarantee that spurious results and inconsistencies that may occur due to uncontrolled service changes are avoided. The presented work provides a unifying theoretical framework for controlling the evolution of services that deals with structural, behavioral and QoS level-induced service changes in a type-safe manner. The goal of the work is to ensure correct version transitions so that previous and future clients can use a service in a consistent manner.