Automated deployment is an important issue in large-scale distributed systems, such as web services choreographies that implement business processes encompassing multiple organizations. In this paper, we present the CHOReOS Enactment Engine, a novel extensible open source middleware system that provides a platform for automation of the distributed deployment of web service horeographies in cloud computing environments. We evaluated the choreographies enactment time experimentally, varying the amount of services to be deployed and the amount of virtual machines available to the deployment process. The CHOReOS Enactment Engine nabled the automated deployment of service compositions on the cloud in an automated and reproducible way.