The healthcare industry generates enormous amounts of complex clinical data that make the prediction of disease detection a complicated process. In medical informatics, making effective and efficient decisions is very important. Data Mining (DM) techniques are mainly used to identify and extract hidden patterns and interesting knowledge to diagnose and predict diseases in medical datasets. Nowadays, heart disease is considered one of the most important problems in the healthcare field. Therefore, early diagnosis leads to a reduction in deaths. DM techniques have proven highly effective for predicting and diagnosing heart diseases. This work utilizes the classification algorithms with a medical dataset of heart disease; namely, J48, Random Forest, and Naïve Bayes to discover the accuracy of their performance. We also examine the impact of the feature selection method. A comparative and analysis study was performed to determine the best technique using Waikato Environment for Knowledge Analysis (Weka) software, version 3.8.6. The performance of the utilized algorithms was evaluated using standard metrics such as accuracy, sensitivity and specificity. The importance of using classification techniques for heart disease diagnosis has been highlighted. We also reduced the number of attributes in the dataset, which showed a significant improvement in prediction accuracy. The results indicate that the best algorithm for predicting heart disease was Random Forest with an accuracy of 99.24%.