The redshift dependence of the structure of massive LCDM halos

(Abridged) We use two very large cosmological simulations to study how the density profiles of relaxed LCDM dark halos depend on redshift and on halo mass. We confirm that these profiles deviate slightly but systematically from the NFW form and are better approximated by the empirical formula, $d\log \rho/d\log r \propto r^{\alpha}$, first used by Einasto to fit star counts in the Milky Way. The best-fit value of the additional shape parameter, $\alpha$, increases gradually with mass, from alpha ~ 0.16 for present-day galaxy halos to alpha~ 0.3 for the rarest and most massive clusters. Halo concentrations depend only weakly on mass at z=0, and this dependence weakens further at earlier times. At z ~3 the average concentration of relaxed halos does not vary appreciably over the mass range accessible to our simulations (M >=3e11Msun). Furthermore, in our biggest simulation, the average concentration of the most massive}, relaxed halos is constant at c200 ~3.5 to 4 for 0<=z<= 3. These results have important implications for currently planned surveys of distant clusters.