Abstract In recent years, sentiment analysis is becoming more and more important as the number of digital text resources increases in parallel with the development of information technology. Feature selection is a crucial sub-stage for the sentiment analysis as it can improve the overall predictive performance of a classifier while reducing the dimensionality of a problem. In this study, we propose a novel wrapper feature selection algorithm based on Iterated Greedy (IG) metaheuristic for sentiment classification. We also develop a selection procedure that is based on pre-calculated filter scores for the greedy construction part of the IG algorithm. A comprehensive experimental study is conducted on commonly-used sentiment analysis datasets to assess the performance of the proposed method. The computational results show that the proposed algorithm achieves 96.45% and 90.74% accuracy rates on average by using Multinomial Naive Bayes classifier for 9 public sentiment and 4 Amazon product reviews datasets, respectively. The results also reveal that our algorithm outperforms state-of-the-art results for the 9 public sentiment datasets. Moreover, the proposed algorithm produces highly competitive results with state-of-the-art feature selection algorithms for 4 Amazon datasets.