A data processing apparatus and method are provided for generating a trace stream. The data processing apparatus comprises logic for producing data elements, and trace logic for producing a stream of trace elements representative of at least some of the data elements. The trace logic has trace generation logic operable to generate trace elements for inclusion in the stream, and is further arranged to generate trace timing indicators for inclusion in the stream. Each trace timing indicator indicates the elapse of one or more processing timing intervals, the processing timing interval being a predetermined plurality of clock cycles.