Dark matter substructure on small scales is currently weakly constrained, and its study may shed light on the nature of the dark matter. In this work we study the gravitational effects of dark matter substructure on measured pulsar phases in pulsar timing arrays (PTAs). Due to the stability of pulse phases observed over several years, dark matter substructure around the Earth-pulsar system can imprint discernible signatures in gravitational Doppler and Shapiro delays. We compute pulsar phase correlations induced by general dark matter substructure, and project constraints for a few models such as monochromatic primordial black holes (PBHs), and Cold Dark Matter (CDM)-like NFW subhalos. This work extends our previous analysis, which focused on static or single transiting events, to a stochastic analysis of multiple transiting events. We find that stochastic correlations, in a PTA similar to the Square Kilometer Array (SKA), are uniquely powerful to constrain subhalos as light as ∼ 10−13 M, with concentrations as low as that predicted by standard CDM.