The non-uniform distribution of classes (imbalanced data) and the presence of irrelevant and/or redundant information are considered as challenging aspects encountered in most real-world domains. In this paper, we propose an efficient software fault prediction (SFP) model based on a wrapper feature selection method combined with Synthetic Minority Oversampling Technique (SMOTE) with the aim of maximizing the prediction accuracy of the learning model. A binary variant of recent optimization algorithm; Queuing Search Algorithm (QSA), is introduced as a search strategy in wrapper FS method. The performance of the proposed model is assessed on 14 real-world benchmarks from the PROMISE repository in terms of three evaluation measures; sensitivity, specificity, and area under the curve (AUC). Experimental results reveal a positive impact of the SMOTE technique in improving the prediction performing in a highly imbalanced data. Moreover, the binary QSA (BQSA) show a superior efficacy on 64.28% of datasets compared with other state-of-the-art algorithms in handling the problem of FS. The combination of BQSA and SMOTE achieved acceptable AUC results (66.47-87.12%).