A flash memory storage device including a memory cell array and a memory control circuit is provided. The memory cell array includes a plurality of well regions. Each of the well regions includes a plurality of memory blocks and a record block. The memory control circuit is coupled to the memory cell array. The memory control circuit is configured to perform an erase operation on the memory blocks of each of the well regions and record erase times of each of the well regions into the respective record block. In addition, a method for operating a flash memory storage device is also provided.