The support of multi-tenancy is an essential requirement for leveraging the full capacity of Cloud computing. Multi-tenancy enables service providers to maximize the utilization of their infrastructure and to reduce the servicing costs per customer, thus indirectly benefiting also the customers. In addition, it allows both providers and consumers to reap the advantages of Cloud-based applications configurable for the needs of different tenants. Nowadays, new applications or services are typically compositions of multiple existing services. Service Composition Engines (SCEs) provide the required functionality to enable the definition and execution of such compositions. Multi-tenancy on the level of SCEs allows for both process model, as well as underlying infrastructure sharing. Towards the goal of enabling multi-tenancy of SCEs, in this paper, we investigate the requirements and define a general architecture for the realization of a multi-tenant SCE solution. This architecture is prototypically realized based on an open-source SCE implementation and integrated into an existing multi-tenant aware Enterprise Service Bus (ESB). The performance evaluation of our prototype shows promising results in terms of the degradation introduced due to processing and communication overhead.