Gossip is a scalable and easy-to-deploy broadcast method for distributed systems. In gossip a broadcast message is disseminated through repeated information exchanges between randomly chosen nodes. Gossip can also achieve high reliability using a large amount of redundant messages, but this also incurs high load on the network. This paper proposes a new gossip algorithm which incorporates network coding techniques to mitigate the high load. With random linear coding, each message propagated in the new algorithm is randomly generated from the broadcast message. Unlike in ordinary gossip, this feature prevents nodes from receiving an identical message more than once, allowing to achieve the same reliability at a lower message cost.