WhatsApp definitely stores your messages on their server. They have to. If you send a WhatsApp message to someone and their phone is off, does it bounce? If not, they are storing your messages at some point.

Just because they say they don't store them forever really doesn't mean much, and I am pretty surprised by how many people on HN keep repeating it.