Traditional approaches to Web service composition have focused on either generating compositions that match the structural and functional requirements of the user, or using quantitative optimization techniques over non-functional attributes. However, users preferences and trade-offs are often qualitative over non-functional attributes of the goal service like security, performance, cost. We propose to capture such requirements as qualitative preferences in addition to structural and functional constraints of the composite goal service. We analyze the theory of CP-nets as a formal model for representing and reasoning with qualitative preferences, and show how it can be used to improve the quality of the generated composition and scalability of the composition algorithm.