Abstract: Ultra-violet completions of the Standard Model often feature a modified cosmology before Big Bang Nucleosynthesis. For example, the energy content of the universe prior to this epoch can be dominated by a non-relativistic particle that eventually decays and reheats the universe at temperatures of a few MeV. This period of early matter domination (EMD) has important consequences for both the amount of dark matter (DM) that is left over, and for the growth of density perturbations. I will discuss such a cosmology in the context of axion-like particle (ALP) dark matter, whose non-thermal nature makes it especially sensitive to these early-universe dynamics. EMD leads to qualitatively different target parameter space for direct detection experiments. I will also show that ALP density perturbations grow much faster during EMD, leading to the formation of dense DM clumps, or minihalos, with characteristic masses below the Earth mass. While extremely rare, Earth encounters with these clumps would lead to enhanced signals in direct detection experiments. These small-scale structures can also be probed with pulsar timing and photometric monitoring of highly magnified extragalactic stars.