Systems and methods for identifying threads of related messages. A computer can associate messages with threads by storing a thread identifier (thread ID) identifying a thread and associating the thread ID with a message identifier (message ID) of each known message that belongs to the thread. The computer can inspect a message to determine whether the message identifies a reference message. Before assigning a thread ID to the message or a reference message, the computer can determine whether a message ID for either message is stored in association with a thread ID. If a thread ID is stored for a message ID of either message, the computer can assign the thread ID to message IDs of other reference messages. If a thread ID is not stored for a message ID of either message or is different for either message, store a common thread ID in association with both messages.