Vibration analysis is an effective tool for the condition monitoring and fault diagnosis of rolling element bearings. Conventional diagnostic methods are based on the stationary assumption, thus they are not applicable to the diagnosis of bearings working under varying speed. This constraint limits the bearing diagnosis to the industrial application significantly. In order to extend the conventional diagnostic methods to speed variation cases, a tacholess envelope order analysis technique is proposed in this paper. In the proposed technique, a tacholess order tracking (TLOT) method is first introduced to extract the tachometer information from the vibration signal itself. On this basis, an envelope order spectrum (EOS) is utilized to recover the bearing characteristic frequencies in the order domain. By combining the advantages of TLOT and EOS, the proposed technique is capable of detecting bearing faults under varying speeds, even without the use of a tachometer. The effectiveness of the proposed method is demonstrated by both simulated signals and real vibration signals collected from locomotive roller bearings with faults on inner race, outer race and rollers, respectively. Analyzed results show that the proposed method could identify different bearing faults effectively and accurately under speed varying conditions.