Permutation entropy (PE) is a new method proposed for detecting the randomicity and dynamic changes of time series, which can be used in the field of fault diagnosis. However, due to the complexity of mechanical systems, the randomicity and dynamic changes of the vibration signal behave on different scales, making it necessary to analyze the vibration signal with permutation entropy in a multi-scale way. Therefore, a new method of rolling bearing fault diagnosis based on PE and the local characteristic-scale decomposition (LCD) is put forward. Firstly, the LCD method is used to decompose the vibration signal, and ISCs spanning different scales are obtained. Secondly, the permutation entropy of the first few ISC components, which contain the main fault information, is calculated. The entropies are accordingly seen as the characteristic vector, then input to the neural network ensemble based classifier. Finally, the proposed method is applied to the experimental data. The analysis results show that the proposed approach can effectively achieve fault diagnosis of rolling bearings.