An experimental study was made on the fatigue behavior of A5083P-O aluminum alloy under various types of superposed random strain waves. Each random strain wave was generated by superposing a Gaussian random process having a specified power spectral density with the peak frequency of 2.42 Hz, on a constant amplitude pulsating trapezoidal wave with the frequency of 0.25 Hz. In all the fatigue tests, including the constant amplitude tests, drastic hardenings of the material were observed. In order to handle them quantitatively, the mean hysteresis energy per cycle was calculated for each specimen. Then it was found the rapidity of the hardening process increased as the RMS value of the Gaussian process, E2RMS, increased. And it was also found the initial value of the mean hysteresis energy was a good parameter to relate the random fatigue test data to the constant amplitude test data, resulting in a fairly good estimation of the fatigue lives. Meanwhile different five types of wave count methods were comparatively examined, namely, range count, hysteresis loop count, rain flow count and two types of peak count (named peak 1 and peak 2 respectively), combined to the modified Miner's law. As a result, the rain flow count method gave the most consistent and acceptable results among all, though the estimations fell on the dangerous side owing to its incapability of estimating the life-reducing effect by the superposition of random waves. Finally, it is to be noted that the above-mentioned life estimation with the initial value of the mean hysteresis energy was still more superior to the one by the rain flow count method and the modified Miner's law.