A storage device includes a nonvolatile memory device that includes memory blocks, each including memory cells, and a controller that receives a first write request from an external host device. Depending on the first write request, the controller transmits a first sanitize command to the nonvolatile memory device and transmits first write data and a first write command associated with the first write request to the nonvolatile memory device. The nonvolatile memory device is configured to sanitize first data previously written to first memory cells of a first memory block of the memory blocks in response to the first sanitize command. The nonvolatile memory device is further configured to write the first write data to second memory cells of the first memory block in response to the first write command.