An apparatus and method for authenticating a Non-Volatile Memory (NVM) device are provided. A host device that authenticates the NVM device transmits challenge information for authentication to the NVM device, receives pieces of authentication information in response to the challenge information from the NVM device, and authenticates the NVM device using the pieces of authentication information by the host device. The pieces of authentication information are generated based on the challenge information and secret key information stored in the NVM device.