Disclosed are various examples for implementations of policy-based trusted peer-to-peer connections. A computing device can receive a message from a first client device, the message specifying a public address of the first client device and an identifier of the second client, device. The computing device can then send a query to a computing device, wherein the query specifies an identifier of the first client device and the identifier of the second client device. The computing device can also determine that the first client device is authorized to communicate with the second client device based on a response to the query received from the second computing device. In some instances, the computing device can then send the public address of the first client device to the second client device.