Complex services can be described by service compositions and executed by service orchestrations. Changing service compositions is a frequent requirement in practical settings. Changing the composition must not result in a violation of its functional or non-functional properties. Whereas functional aspects such as soundness have been studied quite well, non-functional properties such as transactionality have been paid little attention to in the context of change. However, in practical applications it is impossible to separate the aspects of transactionality and change. In this paper, we investigate the effects of applying changes in transactional service compositions. For this we analyze the combination of concepts from the worlds of transactional service compositions and process change. Based on the analysis results, we derive algorithms to deal with change in transactional service compositions. We discuss the algorithm design and their practical applicability.