Web services have acquired enormous popularity among software developers and researchers due to the increasing levels of flexibility required by current distributed applications. However, service search facilities are still rather difficult to use. This paper presents WSQBE, a search method that aims at assisting service discoverers by generating a short list of candidate services and easing query specification. In contrast with previous approaches, WSQBE discovery process is based on a novel search space reduction mechanism. Experimental evaluations of our approach are also reported.