The broad application of service-oriented architecture (SOA) has fueled the rapid growth of web and cloud services and service-based systems (SBSs). Tremendous web and cloud services have been deployed all over the world. Finding the right services becomes difficult and critical. Thus, service recommendation has become of paramount research and practical importance. Existing web service recommendation approaches employ utility functions or skyline techniques. However, those approaches have not addressed a critical and fundamental problem: how to recommend services according to a system engineer’s quality constraints, e.g., response time, failure rate, etc. To address this issue, we first propose two basic personalized quality centric approaches for service recommendation, which employ the k-nearest neighbors and the dynamic skyline techniques respectively. To overcome the respective limitations of the two basic approaches, we propose two hybrid approaches, namely KNN-DSL and DSL-KNN. Extensive experiments are conducted on a real-world dataset to demonstrate the effectiveness and efficiency of our approaches.