Abstract: The evolution of the universe prior to Big Bang Nucleosynthesis could have gone through a phase of early matter domination which enhanced the growth of small-scale dark matter structure. If this period was long enough, self-gravitating objects formed prior to reheating. We study the evolution of these dense early halos through reheating. At the end of early matter domination, the early halos undergo rapid expansion and eventually eject their matter. We find that this process washes out structure on scales much larger than naively expected from the size of the original halos. We compute the density profiles of the early halo remnants and use them to construct late-time power spectra that include these non-linear effects. We evolve the resulting power spectrum to estimate the properties of microhalos that would form after matter-radiation equality. Surprisingly, cosmologies with a short period of early matter domination lead to an earlier onset of microhalo formation compared to those with a long period. In either case, dark matter structure formation begins much earlier than in the standard cosmology, with most dark matter bound in microhalos in the late universe.