It is usual for 802.11 WLAN clients to probe actively for access points in order to hasten AP discovery and to find "hidden" APs. These probes reveal the client's list of preferred networks, thus, present a privacy risk: an eavesdropper can infer attributes of the client based on its associations with networks. We propose an access-point discovery protocol that supports fast discovery and hidden networks while also preserving privacy. Our solution is incrementally deployable, efficient, requires only small modifications to current client and AP implementations, interoperates with current networks, and does not change the user experience. We note that our solution is faster than the standard hidden-network discovery protocol based on measurements on a prototype implementation.