Early fatigue damage in non-unidirectional multi-ply graphite/epoxy composites is manifested by a distribution of cracks and disbonds through the bulk of the material. Such damage is subtle and is difficult to detect with conventional ultrasonic technology. Consequently, a new ultrasonic measurement technique called phase-insensitive tone-burst spectroscopy has been developed. The new technique eliminates problems associated with phase cancellation and pulse shape artifacts inherent to conventional broadband ultrasonic spectral measurement systems and produces clean spectral information irrespective of specimen inhomogeneity or irregularities in surface geometry. Application of the new technique to measurements of graphite/epoxy composites has yielded frequency-domain profiles that show distinct differences in ultrasonic attenuation, attenuation slope, and velocity for each specimen experiencing a different level of fatigue damage.