Cloud computing is a promising utility-based distributed computing environment in which resources (hardware/software) are offered as a service over the Internet on a pay per use basis. It involves elastic resource provisioning capabilities and hence charge only for those Cloud resources that are actually needed. However, true elasticity and cost-effectiveness in the pay-per-use Cloud business model has not been achieved yet. Most of the auto-scaling techniques in Cloud allow horizontal scaling by adding duplicate instances. They do not fully consider both; users' expected performance and pricing of the services. Since, Cloud platforms offer a plethora of server configurations at different pricing, the ability to scale by varied size instances can provide greater elasticity and hence significant improvements in cost and resource utilization. In this work, a heterogeneity-aware auto scaling algorithm that adapts to the workload changes while maintaining the Quality of Service (QoS) is proposed. The proposed method uses online profiling of Cloud resources and workload history to analytically estimate subsequent resource requirements. It then employs a heuristic to provision the smallest set of different size resource configurations in order to meet the QoS targets at reduced cost and improved resource utilization. Simulation based experimental evaluation on representative web and scientific workload patterns indicate that the proposed auto-scaling technique exhibits better performance as compared to the other contemporary horizontal scaling approaches.