As remnants of the earliest stages of structure formation, the smallest dark matter halos provide a unique probe of the evolution of the Universe prior to the onset of Big Bang nucleosynthesis (BBN). I will discuss how the pre-BBN expansion history can enhance the microhalo population, thereby boosting the dark matter annihilation rate if dark matter is a thermal relic. The amplitude of this boost is highly sensitive to the size of the smallest halos, which provides an additional window into the dynamics and particle content of the early Universe. It is therefore possible to use astronomical observations to learn about the origins of dark matter and the evolution of the Universe during its first second. Specifically, observations of the isotropic gamma-ray background restrict dark matter production during an early matter-dominated era or a period of kination.