Service-oriented design supports system evolution and encourages reuse and modularization. A key ingredient of service orientation is the ability to substitute one service by another without reconfiguring the overall system. This chapter aims to give an overview of the state of the art and open challenges in the area of service substitution. Thereby, we restrict ourselves to changes of the service behavior. We present a formal model of service behavior, formalize service substitution, study algorithms to decide service substitution, and provide rules to construct services that are correct by design. Beside analysis at design time, we also investigate analysis at runtime, where we measure the deviation of a running service (or collection of services) from its specification based on recorded event data (e.g., message or transaction logs).