Rolling element bearings (REB) are widely used in all walks of life, and they play an important role in the health operation of all kinds of rotating machinery. Therefore, the fault diagnosis of REB has attracted substantial attention. Fault diagnosis methods based on time-frequency signal analysis and intelligent classification are widely used for REB because of their effectiveness. However, there still exist two shortcomings in these fault diagnosis methods: (1) A large amount of redundant information is difficult to identify and delete. (2) Aliasing patterns decrease the methods’ classification accuracy. To overcome these problems, this paper puts forward an improved fault diagnosis method based on tree heuristic feature selection (THFS) and the dependent feature vector combined with rough sets (RS-DFV). In the RS-DFV method, the feature set was optimized through the dependent feature vector (DFV). Furthermore, the DFV revealed the essential difference among different REB faults and improved the accuracy of fault description. Moreover, the rough set was utilized to reasonably describe the aliasing patterns and overcome the problem of abnormal termination in DFV extraction. In addition, a tree heuristic feature selection method (THFS) was devised to delete the redundant information and construct the structure of RS-DFV. Finally, a simulation, four other feature vectors, three other feature selection methods and four other fault diagnosis methods were utilized for the REB fault diagnosis to demonstrate the effectiveness of the RS-DFV method. RS-DFV obtained an effective subset of five features from 100 features, and acquired a very good diagnostic accuracy (100%, 100%, 99.51%, 100%, 99.47%, 100%), which is much higher than all comparative tests. The results indicate that the RS-DFV method could select an appropriate feature set, deeply dig the effectiveness of the features and more exactly describe the aliasing patterns. Consequently, this method performs better in REB fault diagnosis than the original intelligent methods.