Many Peer-to-peer (P2P) applications such as media broadcasting and content distribution require a high performance overlay structure in order to deliver satisfying quality of service (QoS). Previous approaches to building such overlays either involve non-scalable solutions such as global information and shared contact point, or rely on gossip style membership dissemination, which lacks QoS awareness. In this paper, we present a distributed membership service called RandPeer, which manages membership information on behalf of P2P applications, and allows peers to locate good neighbors based on their QoS characteristics. Using this service, P2P applications can easily construct their overlays in a scalable and QoS aware fashion. We have implemented RandPeer and experimented in both local and wide area environments. Our results show that (1) RandPeer is scalable and robust to highly dynamic P2P memberships; (2) RandPeer has good lookup performance, both in terms of response time and the randomness of peer selection. The latter improves load balancing and failure resilience of P2P applications; (3) when used to improve the performance of a mesh based P2P overlay, RandPeer achieves 10% improvement in just 2 protocol rounds, which is more than 5 times faster than pure random neighbor selections.