According to one embodiment, a storage device comprises a first storage unit having blocks, each including pages, a second storage unit having a free block list, and a free page list, and a control unit. In write data in units of blocks, the control unit generates compressed data blocks by compressing the data in units of blocks, writes the compressed data blocks to the blocks which can be written in accordance with the information held in the free block list, holds, in the free page list, the information about pages existing in free areas which are provided in the blocks holding compressed data blocks and which holds no compressed data blocks. In write data in units of pages, the control unit writes the data in units of pages to pages existing in the free areas, in accordance with the information held in the free page list.