This paper presents a new Service Discovery Protocol (SDP) suitable for Wireless Sensor Networks (WSN). The restrictions that are imposed by ultra low-cost sensor and actuators devices (basic components of a WSN) are taken into account to reach a minimal footprint solution. The WSN communication model we use is based on the picoObject approach which implements a lightweight middleware for WSN on top of standard object oriented middlewares using a small set of interfaces. The proposed SDP uses also this set, so it supposes the minimal overhead for devices and communication protocols, allowing, at the same time, the deployment of a valuable set of services.