A data processing and method are provided for pre-decoding instructions. The data processing apparatus has pre-decoding circuitry for receiving instructions fetched from a memory and for performing a pre-decoding operation to generate corresponding pre-decoded instructions, which are then stored in the cache for access by the processing circuitry. If a pre-decoded instruction crosses a cache line boundary, then checking circuitry in respect of selected types of pre-decoded instruction checks for consistency between the first portion of the pre-decoded instruction stored within a first cache line and a contiguous second portion of the pre-decoded instruction stored within a second cache line. If this consistency check is passed such that the two portions are self-consistent, then the pre-decoded instruction can be further decoded and issued. If the consistency check is failed, or the pre-decoded instruction is not of a type for which consistency checking is supported, then re-generation of the pre-decoded instruction is triggered.