A storage device and method for storage device state recovery are provided. In one embodiment, a storage device commences an authentication process to authenticate a host device. The authentication process comprises a plurality of phases, and the storage device stores the state of the authentication process, wherein the state indicates the phase(s) of the authentication process that have been successfully completed. After a power loss, the storage device retrieves the state of the authentication process and resumes an operation with the host device without re-performing the phase(s) of the authentication process that have been completed.