A nonvolatile memory and a data rewriting method of the nonvolatile memory that can readily detect a state of operation at a time of a system failure due to a power failure or the like and quickly and reliably restore the nonvolatile memory to a normal storage state by a simple method. In the nonvolatile memory including a physical block as a storage unit, the physical block having a data area (1) and a redundant area (2), the redundant area (2) includes: a logical block address storing area (3) for storing an address of a corresponding logical block; a previously used physical block address storing area (4) for storing an address of a physical block to be erased; and a status information storing area (6) for storing status information for distinguishing a state of operation in each stage occurring in performing data rewriting operation on the physical block.