In this study, the uniaxial tension-tension fatigue behavior of fully nanotwinned magnetron sputtered Cu-6wt%Al, Cu-2wt%Al, and Cu-10 wt%Ni is presented. These alloys have average twin thicknesses ranging from 4 to 8 nm, average grain widths from 90 to 180 nm, and tensile strengths from 1 to 1.5 GPa. In the high cycle regime (103 to 107 cycles), the nanotwinned alloys exhibit fatigue strengths ranging from 210 to 370 MPa, which is higher than previously observed in nanotwinned Cu (fatigue strengths between 80 and 200 MPa). Fatigue strengths are normalized by tensile strength for Cu alloys with different microstructures to study the correlation between tensile and fatigue properties. Post-mortem analysis of the materials reveals a newly observed deformation mechanism, where localized detwinning leads to intergranular fracture between columnar grains. Overall, materials displaying detwinning as a deformation mechanism show lower normalized fatigue strengths in comparison to materials that deform with slip band like behavior.