An apparatus and method for fault tolerant Firmware-Over-The-Air (FOTA) update are provided. The method includes computing a checksum for each sector of a partially updated firmware, for each sector of the partially updated firmware, determining a last instruction in an update package that was applied to that sector, based on checksums included in the update package and the computed checksums of the sectors of the partially updated firmware, determining a last instruction of the update package that was applied to the partially updated firmware prior to the interruption based on the last instruction applied to each sector, and resuming the update procedure starting from an instruction immediately following the last applied instruction.