A clock and data recovery circuit includes a voltage controlled oscillator, a frequency detector and a control circuit. The voltage controlled oscillator is configured to generate a clock signal according to a voltage signal. The frequency detector is configured to detect whether increasing a frequency of the clock signal is required according to a plurality of sampling results of the input data signal and accordingly generate a first up control signal. The control circuit is coupled to the voltage controlled oscillator and the frequency detector and configured to adjust the voltage signal according to the first up control signal. The clock and data recovery circuit operates in a data recovery mode after detecting that the frequency of the clock signal is locked, and the frequency detector is configured to detect whether increasing the frequency of the clock signal is required in the data recovery mode.