In the present work, two issues that can complicate a damage detection process are considered: the uncertainties and the intrinsically nonlinear behavior. To deal with these issues, a stochastic version of the Volterra series is proposed as a baseline model, and novelty detection is applied to distinguish the condition of the structure between a reference baseline state (presumed “healthy”) and damaged. The studied system exhibits nonlinear behavior even in the reference condition, and it is exposed to a type of damage that causes the structure to display a nonlinear behavior with a different nature than the initial one. In addition, the uncertainties associated with data variation are taken into account in the application of the methodology. The results confirm that the monitoring of nonlinear coefficients and nonlinear components of the system response enables the method to detect the presence of the damage earlier than the application of some linear-based metrics. Besides that, the stochastic treatment enables the specification of a probabilistic interval of confidence for the system response in an uncertain ambient, thus providing more robust and reliable forecasts.