Preference elicitation is often used in e-services to create product recommendations for their customers. We present an approach for applying preference elicitation techniques for a semi-automatic query generation system for Web service compositions. These techniques are used for identifying the user's demands on the desired Web service composition and furthermore the trade-offs between interdependent or conflicting preferences. In our iterative process the query is automatically (re-)formulated to present results to the user, so that he can detect undesired characteristics and revise his specifications until he is presented a satisfiable result.