A storage device includes a nonvolatile memory with physical blocks each including a plurality of clusters, and a controller that maintains a first table storing a relationship between a logical address and a physical address of the cluster, and a second table storing a relationship between a logical block and physical blocks allocated thereto. The controller performs garbage collection processing which includes copying data read from valid clusters of the first logical block to a destination logical block, erasing all data of the physical blocks of the first logical block, creating a new logical block when the data read contains an uncorrectable error, allocating the physical blocks of the first logical block to the new logical block, updating the second table so that the physical blocks of the first logical block are associated with the new logical block and no physical blocks are associated with the first logical block.