Database-as-a-Service (DBaaS) has gain significant momentum with the prevailing usage of Cloud computing. Multi-tenancy is one of the key features of DBaaS offering, where a large volume of databases with different Service Level Agreement (SLA) requirements are co-located in one environment and sharing resources. As Cloud resources are elastic and resource demands of database requests are unpredictable, it is challenging to decide when and where to place databases in Cloud environment according to their resource requirements. In this paper, we propose a cost-efficient placement algorithm striving to produce placement solution that optimizes multiple objectives considering multi-resource constraints, user preferences and system preferences. The objective is to help DBaaS providers to achieve effective resource allocation among multiple databases, minimize the disturbance to the system caused by database migration, and maximize Cloud resource utilization. The demonstrated online placement technique can be used as decision making reference for DBaaS providers to make optimal resource planning. The effectiveness and efficiency of the algorithm have been verified by intensive simulation experiments and real-case study in IBM cloud platform. © 2012 IEEE.