Freedom of speech is a core value of our society. While it can be exercised anonymously towards undesired observers in the physical world, the Internet is based on unique and nonanonymous identifiers (IDs) for every participant. Anonymity, however, is a crucial requirement to exercise freedom of speech using the Internet without having to face political persecution. To achieve anonymity, messages must be unlinkable to senders an receivers. That means that messages cannot be linked to IDs and other identifying information of senders and receivers. Anonymization services, such as Tor, re-establish anonymity within the Internet such that, for example, web content can be consumed anonymously. Nevertheless, this type of solution embodies two challenges: First, with the appearance of social media, the Internet usage behavior changed drastically from a one producer with many consumers to a many producers with many consumers of content paradigm. Second, a social media website that is used by many producers and many consumers constitutes a single point of failure (SPoF) regarding both availability and anonymity. Such a website may collect producer and consumer profiles, ultimately breaking anonymity. Publish/subscribe (pub/sub) is a message dissemination paradigm well suited to address the first challenge, the many-to-many exchange of content. peer-to-peer (P2P) Pub/Sub eliminates the need for an SPoF and, thus, partially addresses the second challenge as well. However, research addressing anonymity as a security requirement for Pub/Sub has merely scratched the surface. This thesis improves the state-of-the-art in anonymous Pub/Sub in several areas. In particular, the thesis addresses the following aspects of constructing anonymous Pub/Sub systems: (i.) Building blocks that reduce the complexity of constructing anonymous Pub/Sub systems are proposed; (ii.) methods for anonymously establishing Pub/Sub overlay networks are presented; (iii.) a method for inter-overlay optimization to distribute load is introduced; (iv.) methods for optimizing overlays regarding anonymity are proposed, and (v.) anonymity attacks and countermeasures are presented. Contributions. This thesis contributes to the following research categories: Anonymous overlay establishment: An anonymous Pub/Sub system is presented along six self-containing building blocks with the goal of establishing overlay networks that transport notifications from publishers to subscribers. Each building block is discussed in detail with a focus on leveraging related work to realize the building block. For attribute localization, the building block most relevant for establishing overlays, this thesis proposes multiple contributions: the usage of hash chains as a privacy-preserving transaction pseudonym and distance metric; the adaptation of flooding as well as forest fires; and random walks to distribute attribute knowledge. Anonymous overlay optimization: The thesis proposes two optimizations for anonymity and one optimization for balancing the load. The first anonymity optimization, probabilistic forwarding (PF), applies the concept of mimic traffic to the domain of Pub/Sub. The second anonymity optimization, the shell game (SG), shuffles the overlay. Both optimizations prevent an exposure of information to attackers that can gain knowledge about the overlay topology. The load-balancing optimization uses a ring communication and Bloom filters to distribute load among nodes. Anonymity attacks and countermeasures: Several well-known anonymity attacks are adapted to the domain of anonymous Pub/Sub and evaluated in detail. Novel attacks, such as the request/response-attack and the corner attack, are proposed as well and complemented with countermeasures. Evaluation. The proposed mechanisms and attacks are evaluated using a qualitative approach, quantitatively with an extensive simulation, and empirically with a proof of concept (POC) application. The qualitative approach indicates that the presented mechanisms are well-suited to protect anonymity against a malicious insider threat. The quantitative evaluation is performed with the event-based simulation framework OMNeT++. The results show that the presented anonymous Pub/Sub system can protect anonymity, even in case malicious insiders are combined with a global observer of a very strong anonymity threat. The results also reveal in which situations PF or the SG provides the better anonymity protection. Furthermore, the results indicate which capabilities are favorable for an anonymity attacker. An anonymous micro-blogging application for Twitter shows that the presented system can be implemented for a real-world use case: With the application, users exchange tweets via hashtag-overlays, and cryptographic keys via quick response (QR)-codes and near field communication (NFC).