Engineering nano-scale twin boundaries has been recognized as a novel strategy to achieve a superior combination of tensile strength, ductility, and fatigue limit in metallic materials. However, to date, the strain-controlled fatigue behavior of nanotwin (NT)-strengthened metals is still rarely explored, most possibly owing to the difficulty in preparing bulk fatigue samples. In this work, a bulk heterogeneously structured 304 stainless steel (304 SS) containing 30% volume fraction of NT bundles embedded in the micrometer-sized grain matrix was prepared and studied under constant plastic strain amplitude-controlled fatigue tests. A considerable fatigue life and much higher cyclic flow stress level, while maintaining a weaker degree of cyclic softening at larger strain amplitude, was achieved in NT-strengthened 304 SS, compared with its coarse-grained counterpart in the same strain-controlled fatigue tests. This is fundamentally distinct from the more obvious softening behavior of conventional nanostructured metals induced by strain localization at larger strain amplitude. Such exceptional low-cycle fatigue properties were attributed to the presence of a high-strength NT structure associated with novel mechanical stability and its co-deformation with surrounding grains, effectively suppressing strain localization and fatigue crack initiation.