Abstract We consider the problem of locating nearby application peers over the Internet. We define a new peer-location scheme (called Tiers), that scales to large application peer groups. Tiers creates a hierarchy of peers, and provides an efficient and scalable solution to the peer-location problem. Tiers can be implemented entirely in the application-layer and does not require the deployment of either any additional measurement services, or well-known reference points in the network. We have evaluated the performance of Tiers through detailed experiments. Our results show that Tiers is able to locate the nearest peers quickly (≪1 s) and accurately on wide-area Internet-like topologies. We have also compared the performance of Tiers with two other schemes, Beaconing and Distributed Binning, both of which are known to have good performance. Both these techniques are reference-points based schemes and are efficient for overlays with a small number of peers (e.g. ⩽32). Our results show that Tiers significantly outperforms both these schemes. Tiers is particularly efficient for large overlay networks, has an order of magnitude lower control overhead for overlays with 512 peers and still achieves greater accuracy in locating the nearest peers.