Message header spam filtering is described. In an embodiment, a message is received that includes header entries arranged in an ordered sequence which indicates a path by which the message was communicated. The header entries are parsed to categorize each header entry as a header type where the header types are listed in the ordered sequence. A quantity of each different header type is determined, and a determination is made as to whether the message is likely a spam message based at least in part on the quantity corresponding to a particular header type. In another embodiment, a numeric representation of the ordered sequence is created where the numeric representation includes unique integers assigned to each different header type. A determination is made as to whether the message is likely a spam message based at least in part on the numeric representation of the ordered sequence of header types.