As one of the key characteristics of Software as a Service (SaaS), multi-tenancy aims to support massive customers by sharing application instances and databases. To achieve the high economies of scale, one of the most issues needing to be solved in the real industry is that, given a fixed number of nodes, how to optimally place on-boarding tenants to maximize the total supported number of tenants without violating their SLA requirements. This paper focuses on this problem, which is called On-line Tenant Placement Problem (OTPP). In order to calculate the resource consumption of onboarding tenants, a novel resource consumption estimation model for multi-tenant pattern is proposed in this paper. Based on this model, we explore the complexity of OTPP. A robust heuristic is proposed for the OTPP. The simulation experimental results show the high effectiveness and the good efficiency of our algorithm. © 2010 IEEE.