Companies compete with each other to provide the best services that could satisfy their customers. Users’ satisfaction represents a key aspect that companies aim to achieve as it draws either the success or the failure of a company. However, it is necessary to understand what can lead to customers’ satisfaction with a particular company, technology or product. This research aims at (1) predicting customers’ satisfaction with airline companies, (2) identifying the most effective features on airline customers’ satisfaction, and (3) enhancing the prediction accuracy using several different techniques. The dataset of 129,880 customers is used in this research. It includes demographic features and customers’ perceptions. Unlike previous literature, this research suggests many steps to enhance the prediction accuracy of the implemented techniques. This includes handling missing values, dealing with outliers, generating new features, applying feature selection techniques, and integrating a genetic optimizer. Two data mining techniques are applied to predict customers’ satisfaction: the random forest classifier and the K-nearest neighbor classifier. The results show that the random forest classifier, with the application of handling missing values and outliers, normalization, integrating the newly generated features, and implementing a feature selection technique and genetic optimizer outperformed the K-nearest neighbor classifier with an accuracy of 95%. Regarding the new features generated, service quality and engagement are significant predictors of customers’ satisfaction, whereas information quality was not a determinant feature. The research outcomes can help airline companies improve their services and respond to customers’ needs.