Background. Human papillomavirus type 58 (HPV-58) accounts for a much higher proportion of cervical cancers in East Asia than other types. A classification system of HPV-58, which is essential for molecular epidemiological study, is lacking. Methods and results. This study analyzed the sequences of 401 isolates collected from 15 countries and cities. The 268 unique concatenated E6-E7-E2-E5-L1-LCR sequences that comprised 57% of the whole HPV-58 genome showed 4 distinct clusters. L1 and LCR produced tree topologies that best resembled the concatenated sequences and thus are the most appropriate surrogate regions for lineage classification. Moreover, short fragments from L1 (nucleotides 6014–6539) and LCR (nucleotides 7257–7429 and 7540–52) were found to contain sequence signatures informative for lineage identification. Lineage A was the most prevalent lineage across all regions. Lineage C was more frequent in Africa than elsewhere, whereas lineage D was more prevalent in Africa than in Asia. Among lineage A variants, sublineage A2 dominated in Africa, the Americas, and Europe, but not in Asia. Sublineage A1, which represents the prototype that originated from a patient with cancer, was rare worldwide except in Asia. Conclusions. HPV-58 can be classified into 4 lineages that show some degree of ethnogeographic predilection in distribution. The evolutionary, epidemiological, and pathological characteristics of these lineages warrant further study.