(abridged) We study the relation between the density profiles of dark matter halos and their mass assembly histories, using a statistical sample of halos in a high-resolution N-body simulation of the LCDM cosmology. For each halo at z=0, we identify its merger-history tree, and determine concentration parameters c_vir for all progenitors, thus providing a structural merger tree for each halo. We fit the mass accretion histories by a universal function with one parameter, the formation epoch a_c, defined when the log mass accretion rate dlogM/dloga falls below a critical value S. We find that late forming galaxies tend to be less concentrated, such that c_vir ``observed at any epoch a_o is strongly correlated with a_c via c_vir=c_1*a_o/a_c. Scatter about this relation is mostly due to measurement errors in c_v and a_c, implying that the actual spread in c_vir for halos of a given mass can be mostly attributed to scatter in a_c. We demonstrate that this relation can also be used to predict the mass and redshift dependence of c_v, and the scatter about the median c_vir(M,z), using accretion histories derived from the Extended Press-Schechter (EPS) formalism, after adjusting for a constant offset between the formation times as predicted by EPS and as measured in the simulations;this new ingredient can thus be easily incorporated into semi-analytic models of galaxy formation. The correlation found between halo concentration and mass accretion rate suggests a physical interpretation: for high mass infall rates the central density is related to the background density; when the mass infall rate slows, the central density stays approximately constant and the halo concentration just grows as R_vir. The tight correlation demonstrated here provides an essential new ingredient for galaxy formation modeling.