Technologies are described herein for identifying and correlating e-mail messages. The contents of the subject and recipients fields of e-mail messages received at and sent from a computing system are hashed and stored in a database. When an incoming e-mail message is received at the computing system, the contents of its subject and recipients fields are also hashed. A search is then made of the database to locate e-mail messages identified in the database that have a sufficient number of subject and address hash values that match the subject and address hash values generated for the incoming e-mail message so that the messages may be correlated. A correlation is made between the incoming e-mail message and the best matching e-mail message located during the search of the database.