In the service-oriented computing paradigm, business processes can be wrapped and exposed as business services. Business processes and services are subject to changes required by the organizational and regulatory policies changes. A required service change can affect its supporting business processes, and a change occurred in business process can affect the services it supports. In this study, we will provide some insights on the challenging issue in the service-based business process change management. Different from the existing work in the field of workflow change management, this work focuses on the analysis of dependencies between services and their supporting business processes. We present a taxonomy for the changes that can happen in services and business processes based on the proposed service-oriented business process model. A set of change impact patterns are defined based on the study of the dependencies between services and business processes and the identified change types. These change types and the impact patterns then can be used to analyze the necessary change propagation occurring in business processes and services. We provide algorithms for determining the impact scopes affected by the service and process change. A prototype that implements the proposed change management mechanisms is developed.