The emergence of service-oriented computing as a key-enabler of web applications and the subsequent increase in the web services available, has brought to the surface a major disadvantage of service oriented architecture: there is no consistent way for the consumer to select services based on non-functional, quality requirements. Consumers perceive quality through the prism of their own experience and it is important to see how their evaluation of the quality provided is mapped to the specific quality parameters offered by the provider. In order to achieve that, this work suggests to use consumer ratings of the latter parameters so as to create a consumer quality profile and a provider reputation. By correlating this profile with others, it is possible to identify similarities in the service ratings that will lead to a prediction of which service might be the most appropriate for a specific consumer. Based on this rationale, we devised a Service Recommender mechanism and introduced a slight modification in the service lifecycle to accommodate the new Service Recommendation protocol that supports the mechanism.