There is strong observational evidence that the infant Universe experienced a period of accelerated expansion called inflation. Unfortunately, we do not know how inflation ended nor how the Universe evolved between the end of inflation and the onset of Big Bang nucleosynthesis (BBN). As remnants of the earliest stages of structure formation, the smallest dark matter halos provide a unique probe of the density fluctuations generated during the later stages of inflation and the evolution of the Universe shortly after inflation. The absence of early-forming ultra-compact minihalos (UCMHs) establishes an upper bound on the amplitude of the primordial power spectrum on small scales and has been used to constrain inflationary models. I will show how numerical simulations of UCMH formation reveal that these constraints need to be revised because the dark matter annihilation rate within UCMHs is lower than has been assumed. Nevertheless, we have found that minihalos can still provide unrivaled constraints on the small-scale primordial power spectrum. The abundance of minihalos also encodes information about the evolution of the Universe prior to BBN. I will discuss how the pre-BBN thermal history affects the minihalo population and the dark matter annihilation rate within dwarf spheroidal galaxies, making it possible to use gamma-ray observations to learn about the evolution of the Universe during its first second.