This disclosure relates to service discovery using a dynamically configurable Bloom filter. According to some embodiments, various parameters of the Bloom filter may be determined by a first wireless device. The parameters may include a number of services advertised using the Bloom filter, a false positive rate of the Bloom filter, a set of hash functions used with the Bloom filter, and/or a size of the Bloom filter. The Bloom filter may be generated according to the determined parameters. The Bloom filter, along with some or all of the parameters of the Bloom filter, may be transmitted by the first wireless device. A second wireless device may use the Bloom filter as part of a service discovery process to determine whether or not a desired service is available via the first wireless device.