In many ways cloud computing is an extension of the service-oriented computing (SOC) approach to create resilient and elastic hosting environments and applications. Service-oriented Architectures (SOA), thus, share many architectural properties with cloud environments and cloud applications, such as the distribution of application functionality among multiple application components (services) and their loosely coupled integration to form a distributed application. Existing service-based applications are, therefore, ideal candidates to be moved to cloud environments in order to benefit from the cloud properties, such as elasticity or pay-per-use pricing models. In order for such an application migration and the overall restructuring of an IT application landscape to be successful, decisions have to be made regarding (i) the portion of the application stack to be migrated and (ii) the process to follow during the migration in order to guarantee an acceptable service level to application users. In this paper, we present best practices how we addressed these challenges in form of service migration patterns as well as a methodology how these patterns should be applied during the migration of a service-based application or multiples thereof. Also, we present an implementation of the approach, which has been used to migrate a web-application stack from Amazon Web Services to the T-Systems cloud offering Dynamic Services for Infrastructure (DSI).