External messaging attacks are detected using trust relationships. A profile is built for each target within an organization using extracted header data from multiple prior messages. Trust scores are derived for each sender of a message for each target profile, each trust score is derived from a degree and a quantity of communication between the respective sender and the target in the extracted header data. Incoming messages are received and a target and a sender of each incoming message is determined. A trust score is retrieved for the sender from the profile of the target for each incoming message, labels are generated for each of incoming message based on the respective trust score, and the respective label is applied to be visible to the target in association with the message for each respective message.