Massive early-type galaxies have undergone dramatic structural evolution over the last 10 Gyr. A companion paper shows that nearby elliptical galaxies with M*>1.3x10^{11} M_sun generically contain three photometric subcomponents: a compact inner component with effective radius Re<1 kpc, an intermediate-scale middle component with Re~2.5 kpc, and an extended outer envelope with $R_e approx 10$ kpc. Here we attempt to relate these substructures with the properties of early-type galaxies observed at higher redshifts. We find that a hypothetical structure formed from combining the inner plus the middle components of local ellipticals follows a strikingly tight stellar mass-size relation, one that resembles the distribution of early-type galaxies at z~1.5. Outside of the central kpc, the median stellar mass surface density profiles of this composite structure agree closest with those of massive galaxies that have similar cumulative number density at 1.5<z<2.0 within the uncertainty. We propose that the central substructures in nearby ellipticals are the evolutionary descendants of the red nuggets formed under highly dissipative (wet) conditions at high redshifts, as envisioned in the initial stages of the two-phase formation scenario recently advocated for massive galaxies. Subsequent accretion, plausibly through dissipationless (dry) minor mergers, builds the outer regions of the galaxy identified as the outer envelope in our decomposition. The large scatter exhibited by this component on the stellar mass-size plane testifies to the stochastic nature of the accretion events.