The conventional features are not sensitive to the early fault of bearing. Therefore, in this paper a method combining the advantages of Wigner-Ville time-frequency analysis and complex wavelet transform (CWT) is proposed based on the structural difference of time-frequency distribution in different states. Structural similarity index Wigner-Ville distribution-complex wavelet structural similarity (WVD-CWSS) is calculated by the method, which can be employed to quantitatively evaluate the similarity of time frequency distributions in different states. The proposed method is applied on the early damage assessment of bearing. Firstly, the original vibration signal is transformed to Wigner-Ville distribution by using Wigner-Ville time-frequency transform. Secondly, the complex wavelet transform is performed on the Wigner-Ville time-frequency distributions. Finally, the complex wavelet structural similarity index of the two-dimensional distribution structure is calculated. The results for the full lifetime vibration datasets of rolling bearing indicate that the feature extracted in this paper can detect the early damage of the rolling bearing easier than conventional features.