  Pulsar timing provides a sensitive probe of small-scale structure.
Gravitational perturbations arising from an inhomogeneous environment could
manifest as detectable perturbations in the pulsation phase. Consequently,
pulsar timing arrays have been proposed as a probe of dark matter substructure
on mass scales as small as $10^{-11} M_\odot$. Since the small-scale mass
distribution is connected to early-Universe physics, pulsar timing can
therefore constrain the thermal history prior to Big Bang nucleosynthesis
(BBN), a period that remains largely unprobed. We explore here the prospects
for pulsar timing arrays to detect the dark substructure imprinted by a period
of early matter domination (EMD) prior to BBN. EMD amplifies density
variations, leading to a population of highly dense sub-Earth-mass dark matter
microhalos. We use recently developed semianalytic models to characterize the
distribution of EMD-induced microhalos, and we evaluate the extent to which the
pulsar timing distortions caused by these microhalos can be detected. Broadly,
we find that sub-0.1-$\mu$s timing noise residuals are necessary to probe EMD.
However, with 10-ns residuals, a pulsar timing array with just 70 pulsars could
detect the evidence of an EMD epoch with 20 years of observation time if the
reheat temperature is of order 10 MeV. With 40 years of observation time,
pulsar timing arrays could probe EMD reheat temperatures as high as 150 MeV.
