In the present investigation, the evolution of the relative nonlinear parameters beta and gamma were measured during fatigue tests of concrete prisms C50/65. The stress levels chosen range a damage development from progressive to abrupt failure types during the fatigue experiment. Linear ultrasonic parameters like ultrasonic velocity and attenuation were additionally measured during the experiments. The changes in the nonlinear ultrasonic parameters obtained during the measurements indicate changes in the microstructure of the concrete that occur due to the evolution of damage during a fatigue test. The results of this research also show that the increase in attenuation, which is inherent to the damage process in concrete, affects the accuracy of the results of nonlinear measurements. As the damage developed, the harmonics at high frequencies were increasingly attenuated due to the damage. The nonlinear measurements performed on this specific concrete C50/65 show a predominance of the third harmonic over the second harmonic. The cubic nonlinear parameter measurements therefore show well-defined trajectories consistent with the cracking periods of the concrete specimen under fatigue. This predominance of the third harmonic also points to the character of the tested C50/65 concrete as a cubic elastically nonlinear material.