An important prerequisite for service composition is a versatile and efficient service discovery mechanism. The trends in service computing currently point toward a veritable explosion in the number of services that are or will become available as components in compositions of new services—Cloud Computing and the ’Internet of Things’ are just two examples of such new trends. We hypothesize that it will become critical to be able to filter the discovered services with respect to pre- and postconditions, as well as other semantic aspects such as relevance. We have studied the use of goals as a means for describing semantic aspects of services (e.g., their effects). By using goals, services can be described on any arbitrary and useful level of abstraction. By a goal refinement algorithm, goals can be used not only for describing services, but also for improving the performance of service discovery. In this paper, we describe the goal refinement algorithm and our approach to incorporating it into our service discovery machinery.