A clock and data recovery circuit includes a phase detector (PD), a phase frequency detector (PFD), a multiplexer circuit, a conversion stage and an oscillator. The PD detects a difference in phase between a data signal and an oscillating signal to generate a first set of error signals. The PFD detects a difference in phase and frequency between a reference clock signal and the oscillating signal to generate a second set of error signals. The multiplexer circuit selectively outputs the first set of error signals or the second set of error signals as a third set of error signals according to a selection signal. The conversion stage determines a set of gains according to the selection signal, and converts the third set of error signals with the set of gains to generate a set of input signals. The oscillator generates the oscillating signal according to the set of input signals.