Rolling bearings are the key component of rotating machinery. In the early stage of bearing fault, the faint feature is susceptible to environmental noise. Therefore, weak fault characteristics are difficult to be extracted. An early fault diagnosis method based on minimum entropy deconvolution (MED), detrended fluctuation analysis (DFA), and improved K-nearest neighbor (IKNN) is proposed in this paper. First, the MED filter is employed for the enhancement of the fault components which are drowned in the time-domain vibration signal. The DFA method is then used for the extraction of fault features from the enhanced signals. Finally, the proposed IKNN algorithm is applied as the classifier to identify the fault types. Three kinds of early failures occurred in the inner race, cage, and outer race are performed on the bearing test rig. The experimental results show that the average classification accuracy of the proposed diagnosis method can reach 97.5%.