We report on the first (to our knowledge) demonstration of nonlinear dual-frequency-comb spectroscopy. In multi-heterodyne femtosecond Raman-induced Kerr-effect spectroscopy, the Raman gain resulting from the coherent excitation of molecular vibrations by a spectrally narrow pump is imprinted onto the femtosecond laser frequency comb probe spectrum. The birefringence signal induced by the nonlinear interaction of these beams and the sample is heterodyned against a frequency comb local oscillator with a repetition frequency slightly different from that of the comb probe. Such time-domain interference provides multiplex access to the phase and amplitude Raman spectra over a broad spectral bandwidth within a short measurement time.