The repeated loading of a solid leads to microstructural damage that ultimately results in catastrophic material failure. While posing a major threat to the stability of virtually all materials, the microscopic origins of fatigue, especially for soft solids, remain elusive. Here we explore fatigue in colloidal gels as prototypical inhomogeneous soft solids by combining experiments and computer simulations. Our results reveal how mechanical loading leads to irreversible strand stretching, which builds slack into the network that softens the solid at small strains and causes strain hardening at larger deformations. We thus find that microscopic plasticity governs fatigue at much larger scales. This gives rise to a new picture of fatigue in soft thermal solids and calls for new theoretical descriptions of soft gel mechanics in which local plasticity is taken into account.