A key-value storage device includes a nonvolatile memory device and a memory controller. The nonvolatile memory device stores a value, a key which is referenced to identify the value, and key age data which are changed based on an erase operation of the value, and the memory controller that receives an erase command directing erasing of the value corresponding to the key from a host, generates hash data, a size of which is smaller than a size of the key, in response to the erase command, and transmits a complete message to the host. The memory controller accesses the key and the key age data stored in the nonvolatile memory device based on the hash data and erases the value based on the accessed key and the accessed key age data during an idle time after the transmission of the complete message.