Many applications, such as the dissemination of stock quote events, require reliable and totally ordered delivery of broadcast messages to a large number of processes. Recently, gossip-based broadcast algorithms have been praised as an interesting alternative to deterministic broadcast algorithms for such reliable information propagation, by providing an appealing tradeoff between reliability and scalability. However, despite the importance of ordering guarantees, only little work exists on gossip-based broadcast algorithms providing guarantees stronger than (probabilistic) reliability. In fact, it is still not clear how (well) a probabilistic approach marries with such ordering guarantees. In this paper, we present a novel algorithm, called Atomic Probabilistic Broadcast, for totally ordered delivery of broadcast messages to members of large groups. This algorithm is hybrid in the sense that it has both probabilistic and deterministic characteristics: while the propagation of broadcast messages and ordering information is probabilistic, this ordering information is computed deterministically in a decentralized manner, thereby providing availability and consistency. We point out the advantages of such a hybrid approach, in terms of reliability, scalability, and consistency, and convey these through both analysis and simulation.