The results of theoretical and experimental studies of nonlinear optical phenomena in fractal nanostructures are reviewed. Localization of optical excitations in fractal metal nanocomposites, such as colloidal aggregates, self-affine and semicontinuous films, results in strong enhancements of optical nonlinearities. The localized modes of fractals cover a broad spectral range, from the visible to the far-infrared. A number of optical processes are studied such as the Kerr-type nonlinearities, four-wave mixing, second and third harmonic generation and frequency- and polarization-selective photomodification.