The maximum detectable vibration frequency of an optical frequency domain reflectometry (OFDR) system is limited by the tunable rate of the laser source. Unlike uniform sampling with the time-resolved method, the sampling frequency is randomly modulated so that the vibration signal applied on the interrogation fiber is sampled by a multi-frequency sub-Nyquist sampling method and reconstructed by the compressive sensing technique. First, we give a full treatment to prove that the proposed method has the same performance as the conventional method. Second, in a further proof-of-concept experiment, the measurable frequency of a sparse signal is achieved up to 200 Hz with a sweeping rate of 40 nm/s. This method can recover the vibration signal with sampling rates less than that required by the Nyquist sampling theory, which is a significant step toward a high-performance OFDR system, especially for evaluating the intrinsic frequency of the object’s structural condition.