A storage device includes a nonvolatile memory device and a storage controller. The storage controller includes a multi-protocol host interface circuit that receives a first-type request including a first logical address from an external host and transmits/receives data corresponding to the first-type request with the external host by a block unit. Additionally, the multi-protocol host interface circuit receives a second-type request including a first physical address from the external host and transmits/receives data corresponding to the second-type request with the external host by a unit smaller than the block unit. A mapping cache manager manages an address translation table cache, sends an address translation request including the first physical address to the external host, and receives a response including mapping information corresponding to the first physical address from the external host.