Methods, apparatuses and systems directed to a distributed bootstrapping mechanism for peer-to-peer networks. In particular implementations, the de-centralized bootstrapping mechanism utilizes an allocated set of anycast addresses from the public IP space. Routing nodes or peer nodes corresponding to respective autonomous systems select an anycast address by computing a hash of an Autonomous System (AS) number (or other string) and mapping the hash value, or a portion of the hash value, to one of the anycast addresses in the allocated set. Other mechanisms for selecting anycast addresses (such as random selection) can be used. One or more of the routing nodes of the autonomous system may advertise a host route identifying the selected anycast address. When a new peer node is added to the P2P network, it may, upon initialization, transmit discovery messages using the anycast addresses from the allocated set, which may be ultimately routed to one of the peers in the P2P network. One of the responding peers in the P2P network may then be used by the newly initialized peer as a bootstrap resource to join the P2P network.