Methods, systems, and apparatus, including computer programs encoded on computer storage media, for a watermark-based message queue. One of the methods includes receiving a first connection request for messages associated with a user device. A first connection session is established with the user device. A message queue of messages associated with the user device is identified, each message in the message queue is associated with a respective timestamp, and the message queue is associated with a current watermark that identifies a first timestamp. An oldest message in the message queue at the time the first connection session was established is identified. An updated watermark that identifies a second timestamp associated with the oldest message is associated with the message queue. One or more messages that have a timestamp newer than or equal to the first timestamp identified by the current watermark is provided to the user device.