An apparatus comprises a clock and data recovery system, and a loss of lock detector at least partially incorporated within or otherwise associated with the clock and data recovery system. The loss of lock detector is configured to generate a loss of lock signal responsive to phase adjustment requests generated for a clock signal in the clock and data recovery system. By way of example, the loss of lock signal may have a first logic level indicative of the phase adjustment requests occurring at a first rate associated with a lock condition and a second logic level indicative of the phase adjustment requests occurring at a second rate lower than the first rate. Absolute values of respective phase increments each associated with multiple up and down phase requests may be accumulated, and the loss of lock signal generated as a function of the accumulated phase increment absolute values.