Abstract: Millisecond pulsars are known to be very stable clocks, whose fluctuations in the periods of pulses observed over decades do not accumulate. We use the stability of these astrophysical clocks to derive prospects for detecting transiting dark matter substructure from frequency dependent fluctuations in the pulsar period over a 30 year timescale. We apply our results to deterministic and stochastic analysis of transiting primordial black holes as well as project sensitivity to diffuse halos predicted by the CDM paradigm.