Ultrasonic nondestructive evaluation (NDE) technique has been applied to investigate the cyclically deformed microstructures of a Cu and Cu-35Zn alloy. These materials, which had different stacking fault energies, were cyclically deformed in order to examine the ultrasonic reaction with different dislocation substructures. The observation of a dislocation structure using TEM and the measurement of the ultrasonic NDE parameters were performed after various fatigue deformation in order to clarify the relationship between them. The ultrasonic velocity was observed to decrease with increasing fatigue life fraction in both materials, which was attributed to the increasing dislocation density, resulted from the cyclic deformation. The increasing rate of ultrasonic attenuation in Cu with a cell structure that evolved during cyclic deformation was higher than that in the Cu-35Zn alloy, which had a planar array. This suggests that the dislocation cell structure is more sensitive to the change in the ultrasonic parameters than the planar array structure formed during cyclic deformation.