A storage device including a flash memory, and circuitry that manages a logical address and a physical address so as to be converted using a conversion table, writes a logical address and old and new information indicating a timing when the data is written, into the physical address together with the data, writes at least latest old and new information of the old and new information written in the block into a predetermined page of the block, and reestablishes the conversion table by arranging the logical address recorded in each page included in the block and the physical address corresponding to the logical address in association with each other, in chronological order of the latest old and new information read out from each block of the flash memory, at a predetermined reestablishment timing for performing reestablishment of the conversion table.