The present invention provides an apparatus and method for storing instruction set information. The apparatus comprises a processing circuit for executing processing instructions from any of a plurality of instruction sets of processing instructions, each processing instruction being specified by an instruction address identifying that processing instruction's location in memory. A different number of instruction address bits need to be specified in the instruction address for processing instructions in different instruction sets. The apparatus further comprises encoding logic for encoding an instruction address with an indication of the instruction set corresponding to that instruction to generate an n-bit encoded instruction address. The encoding logic is arranged to perform the encoding by performing a computation equivalent to extending the specified instruction address bits to n-bits by prepending a pattern of bits to the specified instruction address bits, the pattern of bits prepended being dependent on the instruction set corresponding to that instruction. Preferably, the encoded instruction address is then compressed. This approach provides a particularly efficient technique for incorporating instruction set information with instruction addresses, and will be useful in any implementations where it is desired to track such information, one example being in tracing mechanisms used to trace the activity of a processing circuit.