An overlay network refers to a network that is implemented as various different virtual resources on a physical network referred to as an underlay network. Diagnostics are performed on the overlay network by injecting diagnostic packets from a source endpoint targeting a target endpoint. These endpoints can be in the overlay network, on-premises with the other endpoint but in a different overlay network, or off-premises form the other endpoint. The diagnostic packets include a data packet encapsulated with a diagnostic encapsulation header that can be removed by a network element in the underlay network to allow processing of the data packet, and then added back on. The network element maintains trace information that is a record of receipt of the diagnostic packet and operations performed on the diagnostic packet. A tracing service collects and analyzes this trace information from the various network elements.