Selecting services from those available according to user preferences plays a important role in Web services composition. Current solutions for service selection focus on selecting services quantitatively. In many domains it is desirable to assess such preference in a qualitative rather than quantitative way. Furthermore, in many practical situations, if the user is reluctant to provide complete preference information or to totally order the values of each attributes in every possible context, it is natural to ask how to model in these incompletely specified cases. This paper uses a qualitative graphical representation tool, called CP-nets, to describe qualitative preference relations in a relatively compact, intuitive, and structured manner under conditional ceteris paribus (all else being equal) preference statements. Our goal is to select the optimal set of services available according to user preference with this technique. Experiment results demonstrate the effectiveness and performance of this approach.