Service discovery in Mobile Ad Hoc Networks is an essential process in order for these networks to be selfconfigurable with zero or minimal administration overhead. In this paper we argue that Service Discovery can be greatly enhanced in terms of efficiency (regarding service discoverability and energy consumption), by piggybacking service information into routing layer messages. Thus, service discovery does not generate additional messages and a node requesting a service, in addition to discovering that service, it is simultaneously informed of the route to the service provider. We extended the Zone Routing Protoco (ZRP) in order to encapsulate service information in its routing messages. Extensive simulations demonstrate the superiority of this routing layer-based service discovery scheme over that of a similar, but application layer based service discovery scheme.