The multi-frequency capability of the Planck satellite provides information both on the integrated history of star formation (via the cosmic infrared background, or CIB) and on the distribution of dark matter (via the lensing effect on the cosmic microwave background, or CMB). The conjunction of these two unique probes allows us to measure directly the connection between dark and luminous matter in the high redshift (1 ≤ z ≤ 3) Universe. We use a three-point statistic optimized to detect the correlation between these two tracers, using lens reconstructions at 100, 143, and 217 GHz, together with CIB measurements at 100-857 GHz. Following a thorough discussion of possible contaminants and a suite of consistency tests, we report the first detection of the correlation between the CIB and CMB lensing. The well matched redshift distribution of these two signals leads to a detection significance with a peak value of 42/19σ (statistical/statistical + systematics) at 545 GHz and a correlation as high as 80% across these two tracers. Our full set of multi-frequency measurements (both CIB auto- and CIB-lensing cross-spectra) are consistent with a simple halo-based model, with a characteristic mass scale for the halos hosting CIB sources of log10(M/M⊙) = 10.5 ± 0.6. Leveraging the frequency dependence of our signal, we isolate the high redshift contribution to the CIB, and constrain the star formation rate (SFR) density at z ≥ 1. We measure directly the SFR density with around 2σ significance for three redshift bins between z = 1 and 7, thus opening a new window into the study of the formation of stars at early times.