The success of non-linear optics relies largely on pulse-to-pulse consistency. In contrast, covariance based techniques used in photoionization electron spectroscopy and mass spectrometry have shown that wealth of information can be extracted from noise that is lost when averaging multiple measurements. Here, we apply covariance based detection to nonlinear optical spectroscopy, and show that noise in a femtosecond laser is not necessarily a liability to be mitigated, but can act as a unique and powerful asset. As a proof of principle we apply this approach to the process of stimulated Raman scattering in alpha-quartz. Our results demonstrate how nonlinear processes in the sample can encode correlations between the spectral components of ultrashort pulses with uncorrelated stochastic fluctuations. This in turn provides richer information compared to the standard non-linear optics techniques that are based on averages over many repetitions with well-behaved laser pulses. These proof-of-principle results suggest that covariance based nonlinear spectroscopy will improve the applicability of fs non-linear spectroscopy in wavelength ranges where stable, transform limited pulses are not available such as, for example, x-ray free electron lasers which naturally have spectrally noisy pulses ideally suited for this approach.