Different screening policies are practiced in order to early detect cervical cancer lesions, including the common cytology, HPV-DNA test and colposcopy. Each exam is characterized by its sensitivity and specificity. Moreover, it has associated direct and indirect costs. Our goal in this project is to identify since what age and with what frequency should a patient be tested with the available exams. Medical guide-lines have already been established to address this problem. However, they do not consider the imperfect information of these tests. We formulate Markov Decision Problem models that incorporate primary screening (cytology or HPV-DNA test) as methods of detection, and type I and II errors of these tests. Our results show that screening policies that outperform the existing guidelines with respect to the total expected quality-adjusted life years can be defined.