An apparatus and method are provided for generating and processing a trace stream indicative of instruction execution by processing circuitry. An apparatus has an input interface for receiving instruction execution information from the processing circuitry indicative of a sequence of instructions executed by the processing circuitry, and trace generation circuitry for generating from the instruction execution information a trace stream comprising a plurality of trace elements indicative of execution by the processing circuitry of instruction flow changing instructions within the sequence. The sequence may include a branch behaviour setting instruction that indicates an identified instruction within the sequence, where execution of the branch behaviour setting instruction enables a branch behaviour to be associated with the identified instruction that causes the processing circuitry to branch to a target address identified by the branch behaviour setting instruction when the identified instruction is encountered in the sequence. The trace generation circuitry is further arranged to generate, from the instruction execution information, a trace element indicative of execution behaviour of the branch behaviour setting instruction, and a trace element to indicate that the branch behaviour has been triggered on encountering the identified instruction within the sequence. This enables a very efficient form of trace stream to be used even in situations where the instruction sequence executed by the processing circuitry includes such branch behaviour setting instructions.