Today, heart-disease is one of the most significant causes of mortality in the world. Thus, the prediction of heart-disease is a critical challenge in the area of healthcare systems. In this study, we aim to select the optimal features that can increase the accuracy of heart-disease prediction. A feature-selection algorithm, which is based on genetic algorithm (GA) and random forest (RF), is proposed to increase the accuracy of RF-based classification and determine the optimal heart-disease-prediction features. The performance of the proposed approach is validated via evaluation metrics, namely, accuracy, specificity, sensitivity, and area under the ROC curve by using a public dataset from the University of California, namely, Cleveland. The experimental results confirm that the proposed approach attained the high heart-disease-prediction accuracies of 95.6% on the Cleveland dataset. Furthermore, the proposed approach outperformed other state-of-the-art prediction methods.