A rapid increase in heart disease has occurred in recent years, which might be the result of unhealthy food, mental stress, genetic issues, and a sedentary lifestyle. There are many advanced automated diagnosis systems for heart disease prediction proposed in recent studies, but most of them focus only on feature preprocessing, some focus on feature selection, and some only on improving the predictive accuracy. In this study, we focus on every aspect that may have an influence on the final performance of the system, i.e., to avoid overfitting and underfitting problems or to solve network configuration issues and optimization problems. We introduce an optimally configured and improved deep belief network named OCI-DBN to solve these problems and improve the performance of the system. We used the Ruzzo-Tompa approach to remove those features that are not contributing enough to improve system performance. To find an optimal network configuration, we proposed a stacked genetic algorithm that stacks two genetic algorithms to give an optimally configured DBN. An analysis of a RBM and DBN trained is performed to give an insight how the system works. Six metrics were used to evaluate the proposed method, including accuracy, sensitivity, specificity, precision, F1 score, and Matthew's correlation coefficient. The experimental results are compared with other state-of-the-art methods, and OCI-DBN shows a better performance. The validation results assure that the proposed method can provide reliable recommendations to heart disease patients by improving the accuracy of heart disease predictions by up to 94.61%.