Cardiovascular diseases are becoming one of the largest causes of natural fatalities around the world today. The major reason for this is attributed to the unhealthy lifestyle trends followed by developed nations and lack of proper diagnostics in developing nations. In this paper, we observe how different diagnostic methods can contribute to building an automated decision support system that will help experts to predict the onset of heart diseases. As with any data analytics problem, we initially try to classify the data based on annotated classes and explore a set of algorithms in that domain. Then, we observe peculiarities of heart disease data, and find that some level of clustering will help increase the accuracy of the algorithm. This leads to the formation of an ensemble, which clubs together suitable clustering and classification algorithms, and we run tests on various disease datasets to evaluate the performance of the algorithms. From the analysis, we can conclude that Bayesian models perform well when supported by clustering algorithms, and they can be generally applied over a range of disease data. Analysis was also done by considering the time taken for making the decision, and found that Bayesian algorithms are competent enough to give a good level of accuracy in reasonable amount of time for cardiovascular diseases. © 2021, Springer Nature Singapore Pte Ltd.