The present disclosure relates to a storage device and a method of operating the same. The storage device includes a memory device including a memory cell array that stores normal data and map data, and a memory controller configured to control overall operation, including program operation, read operation, and erase operation, of the memory device in response to requests from a host. The memory device is configured to, during a map data load operation, transmit first map data to the memory controller by reading the first map data among the map data stored in the memory cell array, and transmit second map data to a page buffer group of the memory device by reading the second map data among the map data.