We have observed a time-correlated frequency fluctuation in non-Markovian dephasing of excitons in InAs quantum dots using a six-wave mixing technique. In this measurement, the arrival times of the excitation pulses were controlled to eliminate the influence of Markovian dephasing and to measure the pure non-Markovian behavior. The experimental result shows that the time correlation of the frequency fluctuation due to exciton-phonon interactions was maintained in the quantum dots for over 10 ps. This long-time correlation is caused by the modification of the phonon coupling distribution.