The cyclic deformation behavior of cryomilled (CM) AA5083 alloys was compared to that of conventional AA5083-H131. The materials studied were a 100 pct CM alloy with a Gaussian grain size average of 315 nm and an alloy created by mixing 85 pct CM powder with 15 pct unmilled powder before consolidation to fabricate a plate with a bimodal grain size distribution with peak averages at 240 nm and 1.8 μm. Although the ultra-fine-grain (UFG) alloys exhibited considerably higher tensile strengths than those of the conventional material, the results from plastic-strain-controlled low-cycle fatigue tests demonstrate that all three materials exhibit identical fatigue lives across a range of plastic strain amplitudes. The CM materials exhibited softening during the first cycle, similar to other alloys produced by conventional powder metallurgy, followed by continual hardening to saturation before failure. The results reported in this study show that fatigue deformation in the CM material is accompanied by slight grain growth, pinning of dislocations at the grain boundaries, and grain rotation to produce macroscopic slip bands that localize strain, creating a single dominant fatigue crack. In contrast, the conventional alloy exhibits a cell structure and more diffuse fatigue damage accumulation.