A novel feature extraction and selection scheme was proposed for hybrid fault diagnosis of gearbox based on S transform, non-negative matrix factorization (NMF), mutual information and multi-objective evolutionary algorithms. Time-frequency distributions of vibration signals, acquired from gearbox with different fault states, were obtained by S transform. Then non-negative matrix factorization (NMF) was employed to extract features from the time-frequency representations. Furthermore, a two stage feature selection approach combining filter and wrapper techniques based on mutual information and non-dominated sorting genetic algorithms II (NSGA-II) was presented to get a more compact feature subset for accurate classification of hybrid faults of gearbox. Eight fault states, including gear defects, bearing defects and combination of gear and bearing defects, were simulated on a single-stage gearbox to evaluated the proposed feature extraction and selection scheme. Four different classifiers were employed to incorporate with the presented techniques for classification. Performances of four classifiers with different feature subsets were compared. Results of the experiments have revealed that the proposed feature extraction and selection scheme demonstrate to be an effective and efficient tool for hybrid fault diagnosis of gearbox.