Summary: In this paper, we propose a novel approach for service retrieval that takes into account the service behavior (described as process model) and relies both on preference satisfiability and structural similarity. User query and target process models are represented as annotated graphs, where user preferences on QoS (Quality of Service) attributes (such as response time, availability and throughput) are modelled by means of fuzzy sets. To avoid empty results, a flexible evaluation method based on fuzzy linguistic quantifiers (such as almost all) is introduced. The retrieved results are easily interpreted by the end users thanks to the clear semantics conveyed by that method. Finally, two families of ranking methods are discussed.