Heterogeneous Wireless Sensor Networks (WSNs) are envisioned to provide different types of services in an open and dynamic environment. This paper presents the design, implementation and evaluation of a service discovery and usage solution for heterogeneous WSNs. The users have the possibility to discover and use the services available in the WSN, while sensor nodes can search for the existing gateways to the outside world in order to signal important events. The WSN self-organizes in a clustered structure that acts as a distributed directory of service registrations. The clustering offers the necessary support to achieve energy-efficient discovery within theWSN.We implement the combined solution on resource-constrained sensor nodes, and we analyse the performance characteristics. The results show that the clustering algorithm has low communication overhead and the service discovery protocol scales with the number of nodes and network density. In addition, we show that the solution is lightweight (both code and data memory footprint) and the the interaction user-WSN is straightforward and intuitive.