We present the first measurement of the correlation between the map of the cosmic microwave background (CMB) lensing potential derived from the emph{Planck} nominal mission data and $zgtrsim 1.5$ galaxies detected by the emph{Herschel}-ATLAS (H-ATLAS) survey covering about $600,hbox{deg}^2$, i.e. about 1.4% of the sky. We reject the hypothesis that there is no correlation between CMB lensing and galaxy detection at a $20,sigma$ significance, 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 $10,sigma$. The galaxy bias parameter, $b$, derived from a joint analysis of the cross-power spectrum and of the auto-power spectrum of the galaxy density contrast is found to be $b=2.80^{+0.12}_{-0.11}$, 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 pm 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 CIB, that 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.