Provided herein may be a storage device and a method of operating the same. A method of operating a memory controller Included in a storage device for processing an unmap request may include receiving an unmap request for requesting deletion of address mapping information for an unmap address from a host, storing the unmap address and prestored unmap-pattern data in a random access memory (RAM), and outputting the unmap-pattern data to the host in response to a read request for the unmap address being inputted.