Web service composition is one of many interesting challenges facing the Semantic Web. In this paper we propose a means of performing automated Web service composition by exploiting generic procedures together with rich qualitative user preferences. To this end, we exploit the agent programming language Golog to represent our generic procedure and a first-order preference language to represent rich qualitative temporal user preferences. From these we generate Web service compositions that realize the generic procedure, satisfying the users hard constraints and optimizing for the users preferences. We prove our approach sound and optimal. Our system, GologPref, is implemented and interacting with services on the Web.