Systems, methods, and computer programs encoded on a computer storage medium, for compressing and decompressing electronic messages in message threads. In one aspect, a method is performed by a system the includes one or more data processing devices. The method includes receiving an outgoing electronic message, determining that the outgoing electronic message is a follow-up message in an electronic message thread, determining, by the system, textual content in the electronic message thread that is available to the decompressing device, determining a correspondence between symbols or groups of symbols in the textual content that is available to the decompressing device and code words in accordance with a coding scheme, compressing the outgoing electronic message using the determined correspondence between the symbols or groups of symbols and the code words, and transmitting the compressed outgoing electronic message.