In this paper, the novel approach combining Hilbert-Huang Transform (HHT) and the multi-scale entropy (MSE) analysis is utilized for diagnosing the roller bearing faults, such as inner race defect, outer race defect and roller defect, under the operating conditions of variable rotation speeds. The vibration signals are first measured through the order tracking technique, so that the signals are sampled with identical angle increment and thus the vibration signals are stationary without the factor of shaft rotation speed. The vibration signals are then decomposed into a number of Intrinsic Mode Functions (IMFs) by using the Empirical Mode Decomposition (EMD) method. The envelope analysis is employed to the IMFs that have amplitude modulation phenomenon. The envelope signals are transformed to the series of different scales by course-grained process and MSE of the series can be calculated. With the extracted features of the MSEs, the decision tree algorithm is utilized to classify the different faulted bearing types and faulted levels.