We present a tomographic cosmic shear analysis of the Kilo-Degree Survey (KiDS) combined with the VISTA Kilo-Degree Infrared Galaxy Survey. This is the first time that a full optical to near-infrared data set has been used for a wide-field cosmological weak lensing experiment. This unprecedented data, spanning 450 deg², allows us to significantly improve the estimation of photometric redshifts, such that we are able to include robustly higher-redshift sources for the lensing measurement, and – most importantly – to solidify our knowledge of the redshift distributions of the sources. Based on a flat ΛCDM model we find S₈ ≡ σ₈ Ω_m/0.3 = 0.737^+0.040_−0.036 in a blind analysis from cosmic shear alone. The tension between KiDS cosmic shear and the Planck-Legacy CMB measurements remains in this systematically more robust analysis, with S₈ differing by 2.3σ. This result is insensitive to changes in the priors on nuisance parameters for intrinsic alignment, baryon feedback, and neutrino mass. KiDS shear measurements are calibrated with a new, more realistic set of image simulations and no significant B-modes are detected in the survey, indicating that systematic errors are under control. When calibrating our redshift distributions by assuming the 30-band COSMOS-2015 photometric redshifts are correct (following the Dark Energy Survey and the Hyper Suprime-Cam Survey), we find the tension with Planck is alleviated. The robust determination of source redshift distributions remains one of the most challenging aspects for future cosmic shear surveys.