A method of operating a key-value storage device includes a key-value storage device receiving from a host a first command including a first key, a first value, and a first snapshot identification (ID), the key-value storage device generating a first snapshot entry including the first snapshot ID, the first key, and a first physical address in a non-volatile memory device at which the first value is written, in response to the received first command, receiving from the host a second command including the first key, a second value, and a second snapshot ID, and in response to the received second command, the key-value storage device generating a second snapshot entry including the second snapshot ID, the first key, and a second physical address in the non-volatile memory device at which the second value is written.