Rolling element bearing (REB) vibration signals under variable speed (VS) have non-stationary characteristics. Order tracking (OT) and time-frequency analysis (TFA) are two widely used methods for REB fault diagnosis under VS. However, the effect of OT methods is affected by resampling errors and close-order harmonic interference, while the accuracy of TFA methods is mainly limited by time-frequency resolution and ridge extraction algorithms. To address this issue, a novel method based on envelope spectrum fault characteristic frequency band identification (FCFBI) is proposed. Firstly, the characteristics of the bearing fault vibration signal’s envelope spectrum under VS are analyzed in detail and the fault characteristic frequency band (FCFB) is introduced as a new and effective representation of faults. Then, fault templates based on FCFB are constructed as reference for fault identification. Finally, based on the calculation of the correlation coefficients between the envelope spectrum and fault templates in the extended FCFB, the bearing fault can be diagnosed automatically according to the preset correlation coefficient criterion. Two bearing VS experiments indicate that the proposed method can achieve satisfactory diagnostic accuracy. The comparison of OT and TFA methods further demonstrates the comprehensive superiority of the proposed method in the overall consideration of accuracy, diagnostic time, tachometer dependency, and automatic degree.