A frequency-locked loop (FLL) system typically employs synchronous digital counters to estimate the frequency discrepancy between the output of a local oscillator and an external reference clock. We present a novel FIFO-based frequency detector as an alternative to such counters. Our FIFO-based frequency detector consists of an asP* control unit and data flip-flops at either ends, with inputs being the reference clock and the divided down oscillator output. Using this frequency detector, we construct an asynchronously controlled FLL, and we compare its performance against a synchronously controlled FLL. The asynchronously controlled design is shown to generate more corrective events, allowing it to frequency lock in comparable time to traditional FLLs. Moreover, the asynchronously controlled FLL provides a simpler design whose counter bit width requirements do not increase with finer frequency resolution specifications. Finally, we also propose a slightly modified FLL design which uses the FIFO-based frequency detector to achieve frequency locking in 80% less time, as compared to traditional FLLs.