Provided are a controller configured to perform secure deletion, a key-value storage device including the controller, and a method of operating the key-value storage device. The key-value storage device includes a non-volatile memory including a plurality of blocks, and a controller configured to control a memory operation on the non-volatile memory, receive a write command including a first key and a first value corresponding to the first key from a host, write data of a file corresponding to the first value to at least one block of the plurality of blocks of the non-volatile memory in response to the write command, receive a secure deletion command for the first value from the host, and erase the at least one block to which the first value is written, in response to the secure deletion command.