We report the first detection of a correlation between gravitational lensing by large scale structure and the thermal Sunyaev-Zeldovich (tSZ) effect. Using the mass map from the Canada France Hawaii Telescope Lensing Survey (CFHTLenS) and a newly-constructed tSZ map from Planck, we measure a non-zero correlation between the two maps out to one degree angular separation on the sky, with an overall significance of 6 sigma. The tSZ maps are formed in a manner that removes primary cosmic microwave background fluctuations and minimizes residual contamination by galactic and extragalactic dust emission, and by CO line emission. We perform numerous tests to show that our measurement is immune to these residual contaminants. The resulting correlation function is consistent with the existence of a warm baryonic gas tracing the large scale structure with a bias b_gas. Given the shape of the lensing kernel, our signal sensitivity peaks at a redshift z~0.4, where half a degree separation on the sky corresponds to a physical scale of ~10 Mpc. The amplitude of the signal constrains the product (b_gas/1)(T_e / 0.1 keV)(n_e / 1 m^-3)=2.01pm 0.31pm 0.21, at redshift zero. Our study suggests that a substantial fraction of the missing baryons in the universe may reside in a low density warm plasma that traces dark matter.