Hybrid cloud deployment can be an attractive option for companies wanting to deploy software services on scalable public clouds, while still assuming local control over sensitive data resources. A hybrid deployment, despite providing better control, is difficult to design since code must be partitioned and distributed efficiently between public and private premises. This paper describes our research into automated partitioning of software services for hybrid clouds. We have identified two specific shortfalls of existing partitioning research which are important to a hybrid cloud setting: (i) inflexibility in placement of software function execution between public/private hosts and (ii) no support for making explicit tradeoffs between monetary cost and performance. We propose a new software profiling and partitioning framework (called MANTICORE) which addresses these problems. Experiments on an open-source Web application show that the new approach ensures better performance without increasing costs.