Information about online presence allows participants of instant messaging (IM) systems to determine whether their prospective communication partners will be able to answer their requests in a timely manner, or not. That is why presence information, combined with the ability to send instant messages, makes IM more personal and closer than other forms of communication such as e-mail. On the other hand, revelation of presence constitutes a potential of misuse by untrustworthy entities. A possible risk is the generation of online logs disclosing user habits. This makes presence information a resource worth protecting. We argue, however, that current IM systems do not take reasonable precautions to protect presence information. We implemented an IM system designed to be robust against attacks to disclose a user’s presence. In contrast to existing systems, it stores presence information in a registry in a way that is only detectable and applicable for intended users and not comprehensible even for the registry itself. We use a distributed hash table (DHT) as registry and apply an anonymous communication network to protect the physical addresses of both senders and receivers of messages.