Our ignorance of the Universe's evolution prior to the onset of Big Bang Nucleosynthesis profoundly limits our understanding of dark matter: we cannot calculate its relic abundance without knowing when the Universe became radiation dominated. Fortunately, there is another probe of the early Universe that could break this degeneracy. I will show how an effectively matter-dominated era prior to the onset of nucleosynthesis can radically enhance the population of microhalos for both thermal and nonthermal dark matter. I will then discuss how the resulting abundance of substructure affects the dark matter annihilation rate, which opens up the possibility of using gamma-ray observations to learn about the reheating of the Universe and the origins of dark matter.