Hybrid clouds, which comprise nodes both in a private cloud and in a public cloud, have emerged as a new model for service providers to deploy their services. However, given Quality-of-Service requirements for each service, the question of on how many private and public nodes to deploy the services in the most cost-effective way remains to be answered. The challenges faced in the hybrid cloud stem from the disparate time-varying requests across multiple services, the different cost structures of both types of nodes, and the performance characteristics of nodes. In this paper, we propose a novel algorithm to dynamically optimize the allocation of private and public nodes across services, with special focus on the performance-cost tradeoff between private and public nodes. The algorithm is based on an analytical cost-performance framework for service deployment in hybrid clouds. Our evaluation results based on trace-driven simulation show that our proposed node allocation algorithm can effectively achieve a good cost-performance ratio, compared to the deployment of purely public and private cloud. © 2012 IEEE.