Service discovery is important in mobile and pervasive computing environments, where the set of resources available to an entity changes dynamically over time. This paper describes a novel context-sensitive approach to service discovery, whereby queries and advertisements can be issued in a context-sensitive manner by using techniques such as query completion, query relaxation, preferences and query persistence. We show how context-aware query completion and query result ranking, when considered together with primitives defined in a query language, allow the construction of context-aware applications and reduce message overhead by producing more relevant query results. The elements of this context-sensitive service discovery protocol are showcased within a shopping centre carpark assistant application.