This letter presents a new gossip-based ad hoc service discovery protocol that uses a novel decentralized, peer-to-peer mechanism to provide mobile devices with the ability to advertise and discover services in an efficient way. Our performance study shows that the proposed protocol appropriately addresses the need of proximal service discovery over a dynamic wireless medium. Copyright © 2006 The Institute of Electronics, Information and Communication Engineers.