Deep learning algorithms are an important part of disease prediction and diagnosis by analyzing health data. If not diagnosed and treated early, symptoms of nutritional anemia can be seen as a common laboratory finding of dyspnea, dizziness, lack of concentration, pale skin color, and life-threatening diseases. In the literature, several data mining techniques have been used for the prediction of nutritional anemia, especially, for the iron deficiency anemia. However, each algorithm does not perform well for every data, and therefore new techniques need to be developed. It is because the characteristics of each dataset are different and their dataset sizes, that is, the number of records and the number of parameters are different. In this study, we propose two hybrid models using genetic algorithm (GA) and deep learning algorithms of Stacked Autoencoder (SAE) and Convolutional Neural Network (CNN) for the prediction of HGB-anemia, nutritional anemia, (iron deficiency anemia, B12 deficiency anemia, and folate deficiency anemia), and patients without anemia. In the proposed GA-SAE and GA-CNN models, the hyperparameters of SAE and CNN algorithms are optimized using GA since it is not easy to determine suitable values of deep learning algorithms. Accuracy, F-score, precision, and sensitivity criteria were used to evaluate the prediction and classification performances of the proposed algorithms. As a result of the experimental evaluations using the dataset, the performance of the proposed GA-CNN algorithm whose layers trained separately and sequentially was found to be better than the performance of the studies proposed in the literature, by a 98.50% accuracy.