Damage detection is one important target in structural health monitoring (SHM). Vibration-based damage detection has attracted more attention in the past decades by tracking the modal parameter changes of objective structures. This paper presents the work on developing a novel Bayesian fast Fourier transform (FFT) method for damage detection using the Bayes factor based on ambient vibration data. Based on the properties of FFT data, the likelihood function and prior probability density function (PDF) can be constructed theoretically based on a Gaussian distribution. The most probable value (MPV) of modal parameters and the associated covariance matrix determined from the ambient vibration data can be integrated into the model developed according to the Bayes factor. A novel damage indicator in the frequency domain is proposed, which can be calculated efficiently using the FFT data and the identified modal parameters. The method is illustrated using synthetic data where a simply supported bridge with 10 elements is simulated. It is found that the damage indicator can identify the damage element in both damage location and extent when moving the sensors installed on the bridge. The proposed method is also applied in a steel truss bridge and an American Society of Civil Engineers (ASCE) benchmark structure. This method can make full use of the FFT data, modal parameters' information, and their posterior uncertainties, providing a new way for future damage detection.