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 memory blocks and a redundant memory block. The memory blocks are configured to store data. The memory control circuit is coupled to the memory cell array. The memory control circuit is configured to perform an erase operation to a current memory block of the memory blocks and record an erase retry count of the current memory block. The memory control circuit determines whether the erase retry count exceeds a threshold value. If the erase retry count exceeds the threshold value, the memory control circuit replaces the current memory block by the redundant memory block erased in advance during a time interval of the erase operation. In addition, an operating method of a flash memory storage device is also provided.