Embodiments of apparatuses and methods for protecting data storage structures from intermittent errors are disclosed. In one embodiment, an apparatus includes a plurality of data storage locations, execution logic, error detection logic, and control logic. The execution logic is to execute an instruction to generate a data value to store in one of the data storage locations. The error detection logic is to detect an error in the data value stored in the data storage location. The control logic is to respond to the detection of the error by causing the execution logic to re-execute the instruction to regenerate the data value to store in the data storage location, causing the error detection logic to check the data value read from the data storage location, and deactivating the data storage location if another error is detected.