We study the concentration of dark matter halos and its evolution in N-body simulations of the standard LCDM cosmology. The results presented in this paper are based on 4 large N-body simulations with about 10 billion particles each: the Millennium-I and II, Bolshoi, and MultiDark simulations. The MultiDark (or BigBolshoi) simulation is introduced in this paper. This suite of simulations with high mass resolution over a large volume allows us to compute with unprecedented accuracy the concentration over a large range of scales (about six orders of magnitude in mass), which constitutes the state-of-the-art of our current knowledge on this basic property of dark matter halos in the LCDM cosmology. We find that there is consistency among the different simulation data sets. We confirm a novel feature for halo concentrations at high redshifts: a flattening and upturn with increasing mass. The concentration c(M,z) as a function of mass and the redshift and for different cosmological parameters shows a remarkably complex pattern. However, when expressed in terms of the linear rms fluctuation of the density field sigma(M,z), the halo concentration c(sigma) shows a nearly-universal simple U-shaped behaviour with a minimum at a well defined scale at sigma=0.71. Yet, some small dependences with redshift and cosmology still remain. At the high-mass end (sigma < 1) the median halo kinematic profiles show large signatures of infall and highly radial orbits. This c-sigma(M,z) relation can be accurately parametrized and provides an analytical model for the dependence of concentration on halo mass. When applied to galaxy clusters, our estimates of concentrations are substantially larger -- by a factor up to 1.5 -- than previous results from smaller simulations, and are in much better agreement with results of observations. (abridged)