In many modern systems, applications or services are realized as compositions of multiple existing services that can be enacted by Service Composition Engines (SCEs), which provide the required functionality to enable their definition and execution. SCEs typically use the capabilities of an Enterprise Service Bus (ESB) which serves as the messaging hub between the composed services aiming at ensuring their integration. Together, an SCE and ESB solution comprise the service middleware required for the definition and execution of service-based composite applications. Offering a service middleware solution as a service creates a PaaS offering that allows the service consumers to share the service middleware solution in a multi-tenant manner. However, multi-tenancy support for service middleware solutions remains an open issue. For this purpose, in this work we introduce a general architecture for the realization of a multi-tenant service middleware PaaS solution. This architecture is prototypically realized based on open-source, multi-tenant ESB and SCE solutions. The resulting service middleware provides configurability for service compositions, tenant-aware messaging, and tenant-based administration and management of the SCE and the ESB. We also present an empirical evaluation of the multi-tenant service middleware with focus on the SCE. The results of these experiments show a performance degradation within acceptable limits when scaling the number of tenants and tenant users.