A trace output unit for collecting, buffering and outputting trace data generated by trace circuitry monitoring processing activities of a data processing apparatus is described. The trace output unit comprises an input for receiving a stream of trace data; a plurality of data stores arranged in parallel with each other for storing the trace data; and storage control circuitry for controlling storage of items of the trace data in the data stores. The control circuitry is configured to route the trace items to selected ones of the data stores and to store control data identifying related trace items stored in different data stores. The trace output unit further comprises output control circuitry configured to identify related trace items stored in different data stores from the stored control data and to recombine the related trace items from different data stores to form an output trace data stream.