A large amount of observations have constrained cosmological parameters and the initial density fluctuation spectrum to a very high accuracy. However, cosmological parameters change with time and the power index of the power spectrum varies with mass scale dramatically in the so-called concordance Lambda CDM cosmology. Thus, any successful model for its structural evolution should work well simultaneously for various cosmological models and different power spectra. We use a large set of high-resolution N-body simulations of a variety of structure formation models (scale-free, standard CDM, open CDM, and Lambda CDM) to study the mass accretion histories (MAHs), the mass and redshift dependence of concentrations and the concentration evolution histories of dark matter halos. We find that there is significant disagreement between the much-used empirical models in the literature and our simulations. According to two simple but tight correlations we find from the simulation results, we develop new empirical models for both the MAHs and the concentration evolution histories of dark matter halos, and the latter can also be used to predict the mass and redshift dependence of halo concentrations. These models are accurate and universal: the same set of model parameters works well for different cosmological models and for halos of different masses at different redshifts and the model predictions are highly accurate even when the histories are traced to very high redshift. These models are also simple and easy to implement. A web calculator and a user-friendly code to make the relevant calculations are available from http://www.shao.ac.cn/dhzhao/mandc.html . We explain why Lambda CDM halos on nearly all mass scales show two distinct phases in their evolution histories.