Provided herein may be a storage device and a method of operating the same. The storage device for additionally securing an over-provisioning area may include at least one memory device, each including first memory blocks and second memory blocks, and a memory controller configured to store system data, stored in the first memory blocks of the at least one memory device, in the second memory blocks when a size of a residual space in a memory area of the at least one memory device is less than a threshold.