A clock data recovery circuit includes an oscillator that outputs a first clock and a second clock having the same frequency and a different phase, and a feedback circuit that controls the oscillator so as to synchronize input data and the first clock, the feedback circuit including a controller that controls the oscillator in response to a frequency difference signal and a phase difference signal, a first difference detector that generates a first difference signal, a second difference detector that generates a second difference signal, and a frequency detector that outputs the frequency difference signal based on the first difference signal and the second difference signal, the frequency detector including a state detector that detects one of the rising state or the falling state, and a state holder that holds a state detected in the first phase and outputs the frequency difference signal.