Multi-tenancy, the sharing of the whole technological stack by different consumers at the same time, allows service providers to maximize resource utilization and reduce servicing costs per customer. Essential components of the contemporary enterprise environment like the Enterprise Service Bus (ESB) are therefore required to raise to the challenge of supporting and enabling multi-tenancy, becoming multi-tenant aware. Towards this goal, in this work we discuss the requirements for multi-tenant ESB solutions as fundamental building blocks in the Platform as a Service (PaaS) Cloud delivery model. Addressing these requirements, we propose a solution for dealing with multiple tenant contexts on the level of middleware, based on which we develop ESB^MT, an implementation agnostic multi-tenant aware ESB architecture that we instantiate based on the Apache ServiceMix ESB open source solution. Evaluating the performance of our proposal required the extension of an ESB benchmark, the results of which for different deployment options we also present in this work.