According to one embodiment, a storage device includes a nonvolatile memory, controller and interface. The nonvolatile memory stores data. The controller controls the operation of the nonvolatile memory. The interface includes first and second input/output units that transmit and receive a signal with respect to a host device. The first and second input/output units are set on the first hierarchy having the same communication function. The interface issues a connection request to the first input/output unit and when the connection request to the first input/output unit is rejected, the interface issues the connection request to the second input/output unit.