Storage devices including a memory device and methods of operating the storage devices are provided. The storage devices may include a controller which is configured to program first bit data and second bit data paired with the first bit data into a memory device. The first bit data may be less significant bit data than the second bit data. The controller may be configured to selectively perform or skip backup of the first bit data when programming the second bit data.