Adhesively bonding iron-based shape memory alloy (Fe-SMA) offers a solution to strengthen fatigue-prone metallic structures and prolong their service life. It is thus crucial to understand the bonded joint failure behavior. In pure Mode I and II, studies have shown that the nonlinear material behavior of the Fe-SMA negatively influences the joint strength. In practical application, pure mode joint failure is unlikely, and a combination of tensile and shear stress—characteristic of mixed-mode—is expected in the adhesive upon failure. To distinguish the influence of the Fe-SMA nonlinearity on the mixed-mode debonding, experimental tests of Fe-SMA and linear elastic CFRP bonded joints are carried out and compared. Mode mixity is introduced via loading eccentricity and reveals a bond strength reduction compared to pure Mode II loading, which is more pronounced for CFRP bonded joints. This result implies that the adherend behavior affects the joint failure behavior subjected to mixed-mode loading. Through the theoretical development of a novel beam-on-foundation model incorporating cohesive zone modeling, the joint failure is considered in light of the Fe-SMA’s nonlinear material deformation. A data-driven approach is selected to calibrate the mixed-mode cohesive zone parameters. The analysis of the results obtained from the calibrated model reveals the mechanism behind the more pronounced bond strength reduction for the CFRP case; the local mode-mixity is higher when nonlinear deformations are involved. These results not only advance the safe application of Fe-SMA bonded patches but also reveal a ductile mechanism that can improve the resilience of repair patches. In addition, the developed theoretical model offers an appealing solution to predict Fe-SMA joint failure under complex loading conditions.