Ni-YSZ anodes for Solid Oxide Fuel Cells are vulnerable to microstructural damage during redox cycling leading to a decrease in the electrochemical performance. This study quantifies the microstructural changes as a function of redox cycles at 800 °C and associates it to the deterioration of the mechanical properties and polarisation resistance. A physically-based model is used to estimate the triple-phase boundary (TPB) length from impedance spectra, and satisfactorily matches the TPB length quantified by FIB-SEM tomography: within 20 redox cycles, the TPB density decreases from 4.63 μm−2 to 1.06 μm−2. Although the polarisation resistance increases by an order of magnitude after 20 cycles, after each re-reduction the electrode polarisation improves consistently due to the transient generation of Ni nanoparticles around the TPBs. Nonetheless, the long-term degradation overshadows this transient improvement due to the nickel agglomeration. In addition, FIB-SEM tomography reveals fractures along YSZ grain boundaries, Ni-YSZ detachment and increased porosity in the composite that lead to irreversible mechanical damage: the elastic modulus diminishes from 36.4 GPa to 20.2 GPa and the hardness from 0.40 GPa to 0.15 GPa. These results suggest that microstructural, mechanical and electrochemical properties are strongly interdependent in determining the degradation caused by redox cycling.