A storage device includes a nonvolatile memory device that includes a plurality of pages, each of which includes a plurality of memory cells, and a controller that receives first write data expressed by 2m states (m being an integer greater than 1) from an external host device. The controller in a first operating mode shapes the first write data to second write data, which are expressed by “k” states (k being an integer greater than 2) smaller in number than the 2m states, performs first error correction encoding on the second write data to generate third write data expressed by the “k” states, and transmits the third write data to the nonvolatile memory device for writing at a selected page from the plurality of pages.