Provided herein may be a storage device and a method of operating the same. The storage device may include a memory device including a plurality of memory blocks, and a memory controller configured to control the memory device and perform a garbage collection operation of securing free blocks in which data is not stored, based on a sum of a number of invalid data blocks and a number of free blocks, among the plurality of memory blocks, wherein the number of invalid data blocks is determined depending on a size of invalid data stored in the plurality of memory blocks.