This paper covers methods for service discovery in multi-hop Bluetooth ad hoc networks, so called scatternets. An efficient service discovery protocol suitable for highly dynamic scatternets is proposed. Extensive simulation results are presented showing that the protocol significantly reduces network traffic. Reducing the network traffic is important as many Bluetooth devices have limited power sources and therefore benefit from keeping links idle in power saving modes. Finally it is explained how the proposed protocol can interact with reactive routing protocols and effectively assist route discovery.