Zr alloys are widely used as cladding materials in light-water reactors because of their low neutron absorption and excellent corrosion resistance. However, achieving high-quality diffusion bonding of Zr alloys at conventional high temperatures is challenging, where grain coarsening and formation of interfacial secondary-phase particles (SPPs) degrade joint performance and may compromise the dimensional accuracy of precision components. This study develops a low-temperature, high-strength diffusion-bonding technique for Zr-4 alloy via surface nanocrystallization, and elucidates the associated microstructural evolution and strengthening mechanisms. A gradient nanostructure (GNS) with a thickness of approximately 70 μm was fabricated on the Zr-4 alloy surface via ultrasonic impact treatment (UIT). The GNS comprised nanograins, nanolamellae, and deformed grains, with high densities of grain boundaries, dislocations, and twins. This surface nanostructure was designed to enhance atomic diffusion, reduce bonding temperature, and improve joint properties. Diffusion-bonding experiments were performed for 30 min at temperatures ranging from 740 ^oC to 800 ^oC under a pressure of 10 MPa. The results revealed that the surface nanograins significantly accelerated interfacial void closure and suppressed SPPs overgrowth and aggregation, resulting in a more dispersed distribution of SPPs along the bonding interface. Abnormal grain growth appeared at 15-100 μm from the bonded interface, with the largest grains reaching up to 7.2 times the size of the matrix grains. This abnormal grain growth is attributed to the uneven distribution of strain energy within the GNS, which enables some grains with energy, orientation, or size advantages to grow preferentially by continuously consuming surrounding finer grains. Fracture behavior analysis revealed that cracks initiated neither at the bonded interface nor within the abnormally large grains, but in the Zr matrix region approximately 130 μm from the interface. These grains exhibited numerous deformation twins and acted as crack propagation barriers by coordinating deformation with the surrounding finer grains. Despite their lower yield strength, the abnormally large grains positively contributed to joint strength through a strengthening mechanism induced by hetero-deformation. The shear strength of the Zr/Zr and GNS-Zr/GNS-Zr joints improved as the bonding temperature increased. The GNS-Zr/GNS-Zr joint achieved the highest shear strength of 376.9 MPa at 800 ^oC. Under the same bonding conditions, GNS-Zr/GNS-Zr joints exhibited 1.2-1.6 times higher shear strength than the Zr/Zr joints, with greater improvements at lower temperatures.