A frequency calibration (FCAL) circuit and a method for calibrating an oscillation frequency of a controllable oscillator are provided. The FCAL circuit includes the controllable oscillator, a divider, a time-to-digital converter (TDC) and a calibration logic. The controllable oscillator generates a controllable oscillation clock according to a calibration code. The divider divides the oscillation frequency of the controllable oscillation clock by a predetermined divisor to generate a divided clock. The TDC converts a first period between first edges of a reference clock and the divided clock into a first period code and converts a second period between second edges of the reference clock and the divided clock into a second period code. The calibration logic compares the first period code and the second period code to generate a comparison result for determining whether the first period is greater or less than the second period, and accordingly controls the calibration code.