We use the Millennium Simulation series to investigate the mass and redshift dependence of the concentration of equilibrium cold dark matter (CDM) halos. We extend earlier work on the relation between halo mass profiles and assembly histories to show how the latter may be used to predict concentrations for halos of all masses and at any redshift. Our results clarify the link between concentration and the ``collapse redshift of a halo as well as why concentration depends on mass and redshift solely through the dimensionless ``peak height mass parameter, $ u(M,z)=delta_{rm crit}(z)/sigma(M,z)$. We combine these results with analytic mass accretion histories to extrapolate the $c(M,z)$ relations to mass regimes difficult to reach through direct simulation. Our model predicts that, at given $z$, $c(M)$ should deviate systematically from a simple power law at high masses, where concentrations approach a constant value, and at low masses, where concentrations are substantially lower than expected from extrapolating published empirical fits. This correction may reduce the expected self-annihilation boost factor from substructure by about one order of magnitude. The model also reproduces the $c(M,z)$ dependence on cosmological parameters reported in earlier work, and thus provides a simple and robust account of the relation between cosmology and the mass-concentration-redshift relation of CDM halos.