The nominal mission maps from the Planck satellite contain a wealth of information about secondary anisotropies in the cosmic microwave background (CMB), including those induced by the thermal Sunyaev-Zel'dovich (tSZ) effect and gravitational lensing. We report the first detection of this cross-correlation signal, which wc measure at 6.2sigma significance using the Planck data. We interpret the signal using halo model calculations, which indicate that the tSZ-CMB lensing cross-correlation is a unique probe of the physics of intracluster gas in high-redshift, low-mass groups and clusters. Our results arc consistent with extrapolations of existing gas physics models to this previously unexplored regime and show clear evidence for contributions from both the one- and two-halo terms, but no statistically significant evidence for contributions from diffuse, unbound gas outside of collapsed halos. Our detection is a direct confirmation that hot, ionized gas traces the dark matter distribution over a wide range of scales in the universe (~0.1-50 Mpc/h).