Service discovery in Mobile Ad Hoc Networks is an essential process in order for these networks to be self-configurable. 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 in routing layer messages. Thus, a node requesting a service in addition to discovering that service, it is simultaneously informed of the route to the service provider. We extend the Zone Routing Protocol in order to encapsulate service information in its routing messages and through extensive simulations we prove the superiority of our routing layer-enhanced service discovery scheme against an application layer-based flooding scheme.