Structural health monitoring (SHM) is an essential technology for maintaining the safety, high performance and operational readiness of civilian and military aircraft. Passive and active SHM methodologies incorporating fiber optic, piezoelectric, dielectric and other types of sensors have been explored for the detection of structural damage resulting from excessive mechanical and/or environmental (e.g. corrosion) loads. One of the promising SHM techniques is embedded ultrasonics in which information on structural health is inferred from records of the elastic waves scattered by structural inhomogeneities or cracks. This approach works well when the damage size exceeds a wavelength of the interrogation signal. As a result, small-scale incipient damage may be difficult to detect using conventional embedded ultrasonics practices. In addition, in complex structures such as the aircraft skin, a large number of structural features (e.g. holes, ribs, etc) opens the possibility of misclassification if features and damage scattered signals exhibit comparable characteristics. To address these limitations of the ultrasonic SHM, we propose to utilize the damageinduced nonlinearity of structural material for discriminating different stages of material deterioration and damage development. A concept of a nonlinear acoustic SHM is introduced that is based on the effect of the nonlinear interaction of elastic waves at the damage interface. This nonlinear interaction results in additional spectral components at the combination frequencies noticeable in the spectrum of the received signal. Amplitudes of the additional spectral components indicate the presence and severity of structural damage. We demonstrate the applicability of the nonlinear acoustic SHM for the detection of material degradation at various scales: from micro/meso damage accumulation to macro scale cracks. Examples of macro-scale damage detection are presented and damage characterization capabilities of the method are highlighted. To determine the sensitivity of the method to the micro/meso scale damage accumulation before the material fracture, we conducted a series of strain-controlled fatigue tests in which deterioration of structural material (aluminum) was monitored simultaneously by assessing the sample’s mechanical characteristics and by measuring the nonlinear acoustic manifestation of structural damage at the combination frequencies. A stable increase of the material nonlinearity was observed during the test, which correlated with the respective decrease of the specimen’s stiffness. Scanning acoustic microscopy and SEM analyses of the experimental samples further support the feasibility of nonlinear acoustic SHM for monitoring material degradation at extremely early stages before the onset of macro-scale disintegration and fracture.