A data processing apparatus and method are provided for reducing trace bandwidth. 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 for generating trace elements for inclusion in the stream, the trace generation logic including compression logic for performing a compression process on at least some trace elements prior to inclusion in the stream. A storage is also provided in association with the trace logic for providing control information which is dependent on an operating environment of the logic producing the data elements. The trace generation logic is arranged to reference that control information in order to adapt the compression process performed by the compression logic having regard to the operating environment. By such an approach, the efficiency of the compression process can be maintained irrespective of the operating environment of the logic producing the data elements.