A system and method for allowing peers to exchange messages with other peers independently of their network location in a peer-to-peer environment. Messages may be transparently routed, potentially traversing partitions (e.g. firewalls and NATs), and using different protocols to reach the destination peers. In one embodiment, any peer node may serve as a relay peer that allows peers inside a partition to have a presence outside the partition and provides a mechanism for peers outside partitions to discover and communicate with peers inside the partitions. In one embodiment, a relay peer may maintain information on routes to other peers and assist in relaying messages to other peers. In one embodiment, any peer may query a relay peer for route information. In one embodiment, messages may include routing information as part of their payloads.