Complex on-chip interconnect fabrics, particularly those that include point-to-point interconnects and coherent routing networks, can present significant challenges for conventional trace techniques that may be applied in an effort to efficiently provide an external debugger with visibility into on-chip interconnect transactions. Embodiments described herein generate and supply separate in-circuit-trace messages including address messages and data messages, which are sent out (i.e., off-chip) to external debug tools generally without delay and coincident with the distinct, but related, trace events within address and data paths of the interconnect fabric. These separate message instances embed appropriate tag and mark values to allow the message instances to be post-processed and correlated by the external debug tools so as to reconstruct the transaction information for operations performed in the on-chip interconnect.