As remnants of the earliest stages of structure formation, the smallest dark matter halos provide a unique probe of the density fluctuations generated during 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 Big Bang nucleosynthesis (BBN). I will discuss how the pre-BBN thermal history can enhance the minihalo population, thereby boosting the dark matter annihilation rate if dark matter is a thermal relic. Conversely, the nonthermal production of dark matter can suppress the small-scale power spectrum. It is therefore possible to use gamma-ray observations and observations of the Lyman-α forest to learn about the origins of dark matter and the evolution of the Universe during its first second.