Accurately predicting structural properties of dark matter halos is one of the fundamental goals of modern cosmology. We use the new suite of MultiDark cosmological simulations to study the evolution of dark matter halo density profiles, concentrations, and velocity anisotropies. The MultiDark simulations cover a large range of masses 1e10-1e15Msun and volumes upto 50Gpc**3. The total number of dark matter halos in all the simulations exceeds 60 billion. We find that in order to understand the structure of dark matter halos and to make ~1% accurate predictions for density profiles, one needs to realize that halo concentration is more complex than the traditional ratio of the virial radius to the core radius in the NFW profile. For massive halos the averge density profile is far from the NFW shape and the concentration is defined by both the core radius and the shape parameter alpha in the Einasto approximation. Combining results from different redshifts, masses and cosmologies, we show that halos progress through three stages of evolution. (1) They start as rare density peaks that experience very fast and nearly radial infall. This radial infall brings mass closer to the center producing a high concentrated halo. Here, the halo concentration increases with the increasing halo mass and the concentration is defined by the alpha parameter with nearly constant core radius. Later halos slide into (2) the plateau regime where the accretion becomes less radial, but frequent mergers still affect even the central region. Now the concentration does not depend on halo mass. (3) Once the rate of accretion slows down, halos move into the domain of declining concentration-mass relation because new accretion piles up mass close to the virial radius while the core radius is staying constant. We provide accurate analytical fits to the numerical results for halo density profiles and concentrations.

22 pages, 23 figures, accepted by MNRAS