When linked data applications communicate, they commonly use messaging technologies in which the message exchange itself is not represented as linked data, since it takes place on a different architectural level. When a message cannot be verified and traced on the linked data level, trust in data is moved from message originators to service providers. However, there are use cases in which the actual message exchange and its verifiability are of importance. In such situations, the separation between application data and communication data is not desirable. To address this, we propose messaging based on linked data, where communicating entities and their messages are represented as interconnected Web resources, and we show how conversations can be made verifiable using digital signatures.