Service discovery in traditional networks is realized either by broadcasting requests in the network or by a central entity that holds the necessary information of every service in the network. These techniques are applicable in wireless networks as well, however, only under certain limiting conditions. The authors present a generic overlay that caters to the special requirements of providing and discovering services in wireless mesh networks. The focus of the approach lies on maintaining scalability in large-scale dynamic networks as well as routing efficiency with regard to the communication characteristics of the underlying network.