A data processing system and method includes a data processor and memory that are coupled to debug circuitry that generates debug messages including address translation trace messages. A memory management unit (MMU) includes a translation lookaside buffer (TLB) for implementing address translation to translate addresses between virtual and physical forms. The debug circuitry includes message generation circuitry coupled to the MMU for receiving notice when TLB entries are modified and generating both an address translation trace message and a corresponding program correlation message containing at least one of branch history information and instruction count information. The branch history information is a history of direct branch instructions that are executed and whether, when executed, the direct branch instructions were taken. The instruction count information is a count of one or more data processing instructions executed up to a point in time when a new TLB entry is established in the TLB.