As remnants of the earliest stages of structure formation, the smallest dark matter halos provide a unique probe of the primordial density fluctuations generated during inflation and the evolution of the early Universe. The absence of early-forming ultra-compact minihalos (UCMHs) places powerful constraints on inflationary models. I will show how numerical simulations of UCMH formation reveal that these constraints need to be revised. The abundance of microhalos also encodes information about the evolution of the Universe prior to Big Bang nucleosynthesis (BBN). I will discuss how the pre-BBN thermal history affects the dark matter annihilation rate, making it possible to use gamma-ray observations to learn about the evolution of the Universe during its first second.