The National Institute of Standards and Technology (NIST) defines scalability, resource pooling and broad network access as the main characteristics of cloud computing which provides highly available, reliable, and elastic services to cloud clients. In addition, cloud clients can lease compute and storage resources on a pay-as-you-go basis. The elastic nature of cloud resources together with the cloud’s pay-as-you-go pricing model allow the cloud clients to merely pay for the resources they actually use. Although cloud’s elasticity and its pricing model are beneficiary in terms of cost, the obligation of maintaining Service Level Agreements (SLAs) with the end users necessitates the cloud clients to deal with a cost/performance trade-off. Auto-scaling systems are developed to balance the trade-off between the cost and the performance by automatically provisioning compute and storage resources for the cloud services. Rule-based systems are currently the most popular auto-scaling systems in the industrial environments. However, rule-based systems suffer from two main shortcomings: a) reactive nature, and b) the difficulty of configuration. This thesis proposes an auto-scaling system which overcomes the shortcomings of the rule-based systems. The proposed auto-scaling system consists of a self-adaptive prediction suite and a cost driven decision maker. The prediction suite remedies the first shortcoming (i.e., the reactive nature) of the rule-based systems by forecasting the near future workload of the cloud service. In addition, the cost driven decision maker uses a genetic algorithm to automatically configure the rule-based decision makers. The evaluation results show that the proposed system reduces the total auto-scaling cost up to 25% compared with the Amazon auto-scaling system.