Abstract 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 ΛCDM, QCD axion miniclusters, models with early matter domination, and vector DM produced during inflation. We show that ΛCDM, largely due to tidal stripping effects in the Milky Way, is out of reach for PTAs. 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⁻¹⁶ GeV. We also make publicly available a Python Monte Carlo tool for generating the PTA time delay signal from any model of DM substructure.