This invention includes a system and method to enable a device to determine the presence information of another device over a secure communication network. First, the device and a presence server establish a secure connection. Next, while the initial secure connection with the presence server is established, the device generates a randomly created token and provides it to the presence server. The token is used as a shared-secret by the device and the presence server to secure future presence communications over a non-secure connection. Next, without the need to again enter a password or establish a secure connection with the presence server, the device uses the shared-secret to sign, encrypt and convey presence information to the presence server over an arbitrary connection. Finally, the presence server may share the first device's presence information with another device.