Based on observations obtained with Planck (http://www.esa.int/Planck), an ESA science mission with instruments and contributions directly funded by ESA Member States, NASA, and Canada.-- et al. ; We present the first measurement of the correlation between the map of the cosmic microwave background (CMB) lensing potential derived from the Planck nominal mission data and galaxies detected by the Herschel-ATLAS (H-ATLAS) survey covering about , i.e., about 1.4% of the sky. We reject the hypothesis that there is no correlation between CMB lensing and galaxy detection at asignificance, checking the result by performing a number of null tests. The significance of the detection of the theoretically expected cross-correlation signal is found to be. The galaxy bias parameter, b, derived from a joint analysis of the cross-power spectrum and of the autopower spectrum of the galaxy density contrast is found to be , consistent with earlier estimates for H-ATLAS galaxies at similar redshifts. On the other hand, the amplitude of the cross-correlation is found to be a factor 1.62 ± 0.16 higher than expected from the standard model and also found by cross-correlation analyses with other tracers of the large-scale structure. The enhancement due to lensing magnification can account for only a fraction of the excess cross-correlation signal. We suggest that part of it may be due to an incomplete removal of the contamination of the cosmic infrared background, which includes the H-ATLAS sources we are cross-correlating with. In any case, the highly significant detection reported here using a catalog covering only 1.4% of the sky demonstrates the potential of CMB lensing correlations with submillimeter surveys. ; We gratefully acknowledge support from INAF PRIN 2012/2013 >Looking into the dust-obscured phase of galaxy formation through cosmic zoom lenses in the Herschel Astrophysical Terahertz Large Area Survey,> and from ASI/INAF agreement 2014-024 R.0. F.B. acknowledges partial support from the INFN-INDARK initiative. L.D., R.J.I., and S.M. acknowledge support from the European Research Council (ERC) in the form of Advanced Investigator Program COSMICISM. J.G.N. acknowledges financial support from the Spanish CSIC for a JAE-DOC fellowship, cofunded by the European Social Fund. The work has been supported in part by the Spanish Ministerio de Ciencia e Innovacion, AYA2012-39475-C02-01, and Consolider-Ingenio 2010, CSD2010-00064, projects. ; Peer Reviewed