The present invention extends to methods, systems, computer program products, and data structures for efficiently storing and accessing electronic messages representing fax transmissions. The messages are extended according to a fax schema that defines formats for adding fax protocol specific and/or or fax application specific data fields to an electronic message. According to the fax schema, the messages have relationships with other data fields stored using other schemas that define the accounting services, message content, and message participants associated with the fax transmission. The fax schema promotes efficient storage and access of electronic messages representing fax transmissions, while also facilitating integrating messages received by fax transmission with other types of existing message protocols and message applications.