Purpose: This paper presents a new Service Discovery Protocol (SDP) suitable for Wireless Sensor Networks (WSN). The constraints imposed by ultra low-cost sensor and actuators devices (basic components of a WSN) are taken into account to minimize the overall footprint. Design/methodology/approach: It is based on the lightweight WSN communication model used by picoObjects, a tiny implementation of the distributed object concept. We consistently follow the same design criteria aiming at minimal overhead for devices and communication protocols. In spite of its simplicity it is powerful enough to deploy a valuable set of services. Findings: This approach provides a remote interface that client applications can use without knowing where the service is implemented (platform and location independence). Research limitations/implications: The future work is mainly focused on integrating third party services using different SDPs, making it possible the real deployment of large heterogeneous pervasive environments. Practical implications: Designers may change the underlying SDP model (e.g. centralized vs. distributed) without affecting applications by just tweaking configuration settings. Originality/value: Embedded devices can participate in the Service Discovering Procedure providing their own services by means of standard distributed objects. Besides, the protocol is suitable for any kind of dynamic networked system.