The aim of this study was to describe cervical cancer mortality trends in Brazil for the period 1981-2006. Cervical cancer mortality was corrected on the basis of proportional redistribution of the deaths from "malignant neoplasm of uterus, part unspecified". Time trends were evaluated by means of simple linear regression. After correction, cervical cancer ranked second among the leading causes of death from cancer in the female population up to 2005, with a downward trend for the country as a whole, a decline in the State capitals, and a stable trend in the municipalities in the interior. A downward trend was confirmed in the State capitals in all geographic regions of the country. In the municipalities in the interior, there was an increase in the North and Northeast regions, a decline in the Southeast and South, and a stable trend in the Central-West. Although uneven, the decline began to take consistent shape in the country. Even better results could be achieved by investing in the expansion of screening coverage, especially among the populations at greatest risk.