Cervical cancer (CxCa) is often the result of underestimated abnormalities in the test Papanicolaou (Pap test). The recent advances in the study of the human papillomavirus (HPV) infection (the necessary cause for CxCa development) have guided clinical practice to add HPV related tests alongside the Pap test. In this way, today, HPV DNA testing is well accepted as an ancillary test and it is used for the triage of women with abnormal findings in cytology. However, these tests are either highly sensitive or highly specific, and therefore none of them provides an optimal solution. In this Letter, a clinical decision support system based on a hybrid genetic algorithm – Bayesian classification framework is presented, which combines the results of the Pap test with those of the HPV DNA test in order to exploit the benefits of each method and produce more accurate outcomes. Compared with the medical tests and their combinations (co-testing), the proposed system produced the best receiver operating characteristic curve and the most balanced combination among sensitivity and specificity in detecting high-grade cervical intraepithelial neoplasia and CxCa (CIN2+). This system may support decision-making for the improved management of women who attend a colposcopy room following a positive test result.