In a world where the requirements of computing systems are rapidly changing, the need for a dynamic, yet a cost-effective system becomes urgent. Besides, the need of dynamically scale-up and scale-down, mobility, and reduce both individuals and enterprises share costs and expenses. Thus, such needs and more are fulfilled by Cloud Computing. Mostly, Cloud Computing is promoted as a new paradigm which offers a set of benefits for both providers and consumers. For service providers, it gives an ease of management, reduced maintenance and operational costs, better utilisation of resources, and extra profit. For customers, it offers on demand resources, mobility and effective scale-up, and scale-down. Despite the benefits provided by Cloud Computing, some challenges are seen. For instance, security is a major challenge. Indeed, security is an obstacle to promoting public Clouds for large consumers (i.e. governments and enterprises). Therefore, more research on safety issues in Cloud Computing is required. For instance, the issues of access control could be found in traditional systems; however, Multi-Tenancy could be considered a unique issue related to Cloud Computing. Nonetheless, the research shows for the first time the size of Multi-Tenancy as a security concern. Specifically, Multi-Tenancy could increase the probability of being under attack by 100%. Moreover, to enhance the safety of Multi-Tenancy, availability could compromise as well the Cloud provider’s profit. Although Multi-Tenancy is a complex issue due to its benefits to Cloud Computing, we develop a scheme to enhance the security of Multi-Tenancy while preserving its benefits.