This work is motivated by the need for visual information extraction and management in the growing field of medical image archives. In particular the work focuses on a unique medical repository of digital cervicographic images (Cervigrams) collected by the National Cancer Institute (NCI) in a longitudinal multi-year study carried out in Guanacaste, Costa Rica. NCI together with the National Library of Medicine (NLM) is developing a unique Web-based database of the digitized cervix images to study the evolution of lesions related to cervical cancer. Such a database requires specific tools that can analyze the cervigram content and represent it in a way that can be efficiently searched and compared. We present a multi-step scheme for segmenting and labeling regions of medical and anatomical interest within the cervigram, utilizing statistical tools and adequate features. The multi-step structure is motivated by the large diversity of the images within the database. The algorithm identifies the cervix region within the image. It than separates the cervix region into three main tissue types: the columnar epithelium (CE), the squamous epithelium (SE), and the acetowhite (AW), which is visible for a short time following the application of acetic acid. The algorithm is developed and tested on a subset of 120 cervigrams that were manually labeled by NCI experts. Initial segmentation results are presented and evaluated.