Heart diseases are serious problem in many countries worldwide. In Malaysia, it has been a major killer since 1980. Many health conditions are closely related to heart disease. However, a large amount of data that medical centers have collected each year is not well-mined to find connections between them that can aid in the prognosis of heart disease. Therefore, the purpose of this study is to propose a predictive model of heart disease based on machine learning for prognosis to help individuals with symptoms to seek early advice and treatment. By following the Knowledge Discovery in Database (KDD) methodology that includes data selection, data pre-processing, data transformation, data mining, and interpretation or evaluation of acquired knowledge, this study has tested a dataset taken from UCI Machine Learning Repository. The classification of Artificial Neural Network and Random Forest was used. They were selected based on their adequacy in the medical field, particularly in the aspect of prognosis and diagnosis. The accuracy results obtained by the relevant works from previous authors are also high and reliable. This study uses a few ways to determine the maximum accuracy achieved by both algorithms: dataset splitting and K-Fold Cross-Validation. The results of the study on the test set that has been subdivided into several subsets showed that Artificial Neural Network and Random Forest produced stable accuracies by reaching 67.9% and 64.6%, respectively. The accuracy shown by the Artificial Neural Network is more stable for both subsets, training, and testing sets. In conclusion, Artificial Neural Network has been selected as the algorithm capable of working well with the Heart Disease Prediction Model, referring to the accuracy of the test set, which is slightly better than Random Forest.