Provided herein may be a storage device and a method of operating the same. A memory controller may include a command processor configured to generate a flush command in response to a flush request and determine flush data chunks to be stored, a write operation controller configured to control memory devices to perform a first program operation of storing flush data chunks, and to perform a second program operation of storing data corresponding to a write request that is input later than the flush request, regardless of whether a response to the flush command has been provided to a host, and a flush response controller configured to, when the first program operation is completed, provide a response to the flush command to the host depending on whether responses to flush commands, input earlier than the flush command, have been provided to the host.