  Models of Dark Matter (DM) can leave unique imprints on the Universe's small
scale structure by boosting density perturbations on small scales. We study the
capability of Pulsar Timing Arrays to search for, and constrain, subhalos from
such models. The models of DM we consider are ordinary adiabatic perturbations
in $\Lambda$CDM, QCD axion miniclusters, models with early matter domination,
and vector DM produced during inflation. We show that $\Lambda$CDM, largely due
to tidal stripping effects in the Milky Way, is out of reach for PTAs (as well
as every other probe proposed to detect DM small scale structure). Axion
miniclusters may be within reach, although this depends crucially on whether
the axion relic density is dominated by the misalignment or string
contribution. Models where there is matter domination with a reheat temperature
below 1 GeV may be observed with future PTAs. Lastly, vector DM produced during
inflation can be detected if it is lighter than $10^{-16} \,{\rm GeV}$. We also
make publicly available a Python Monte Carlo tool for generating the PTA time
delay signal from any model of DM substructure.
