Abstract We have used X-ray data from the Neutron Star Interior Composition Explorer (NICER) to search for long-timescale temporal correlations (“red noise”) in the pulse times of arrival (TOAs) from the millisecond pulsars PSR J1824−2452A and PSR B1937+21. These data more closely track intrinsic noise because X-rays are unaffected by the radio-frequency-dependent propagation effects of the interstellar medium. Our search yields strong evidence (natural log Bayes factor of 9.634 ± 0.016) for red noise in PSR J1824−2452A, but the search is inconclusive for PSR B1937+21. In the interest of future X-ray missions, we devise and implement a method to simulate longer and higher-precision X-ray data sets to determine the timing baseline necessary to detect red noise. We find that the red noise in PSR B1937+21 can be reliably detected in a 5 yr mission with a TOA error of 2 μs and an observing cadence of 20 observations per month compared to the 5 μs TOA error and 11 observations per month that NICER currently achieves in PSR B1937+21. We investigate detecting red noise in PSR B1937+21 with other combinations of observing cadences and TOA errors. We also find that time-correlated red noise commensurate with an injected stochastic gravitational-wave background having an amplitude of A _GWB = 2 × 10⁻¹⁵ and spectral index of timing residuals of γ _GWB = 13/3 can be detected in a pulsar with similar TOA precision to PSR B1937+21. This is with no additional red noise in a 10 yr mission that observes the pulsar 15 times per month and has an average TOA error of 1 μs.