A processor and method for handling out-of-order instructions is provided. In one embodiment, the processor comprises instruction pre-fetch logic configured to pre-fetch instructions from memory. The processor further comprises instruction information logic configured to store information about instructions fetched from memory. The processor further comprises control logic configured to control temporary storage of the information related to a pre-fetched instruction if there is currently an active memory access and the currently pre-fetched instruction is an out-of-order instruction. The method pre-fetches the out-of-order in instruction, temporarily stores information associated with the out-of-order instruction in a storage location, and if the memory access completes without encountering a data fault, then saves the temporarily stored information and processes the pre-fetched instruction.