Nonlinear guided waves have been studied extensively for the characterization of micro-damage in plate-like structures, such as early-stage fatigue and thermal degradation in metals. Meanwhile, an increasing number of studies have reported the use of nonlinear acoustic techniques for detection of impact damage, fatigue, and thermal fatigue in composite structures. Among these techniques, the (relative) acoustic nonlinearity parameter, extracted from acousto-ultrasonic waves based on second-harmonic generation, has been considered one of the most popular tools for quantifying the detection of nonlinearity in inspected structures. Considering the complex nature of nonlinearities involved in composite materials (even under healthy conditions), and operational/environmental variability and measurement noise, the calculation of the relative acoustic nonlinearity parameter (RANP) from experimental data may suffer from considerable uncertainties, which may impair the quality of damage detection. In this study, we aim to quantify the uncertainty of the magnitude of the RANP estimator in the context of impact damage identification in unidirectional carbon fiber laminates. First, the principles of nonlinear ultrasonics are revisited briefly. A general probability density function of the RANP is then obtained through numerical evaluation in a theoretical setting. Using piezoelectric wavers, continuous sine waves are generated in the sample. Steady-state responses are acquired and processed to produce histograms of the RANP estimates before and after the impact damage. These observed histograms are consistent with the predicted distributions, and examination of the distributions demonstrates the significance of uncertainty quantification when using the RANP for damage detection in composite structures.