In recent years, next generation sequencing (NGS) technology has been widely used for the discovery of novel human papillomavirus (HPV) genotypes, variant characterization and genotyping. Here, we compared the analytical performance of NGS with a commercial PCR-based assay (Anyplex II HPV28) in cervical samples of 744 women. Overall, HPV positivity was 50.2% by the Anyplex and 45.5% by the NGS. With the NGS, we detected 25 genotypes covered by Anyplex and 41 additional genotypes. Agreement between the two methods for HPV positivity was 80.8% (kappa = 0.616) and 84.8% (kappa = 0.652) for 28 HPV genotypes and 14 high-risk genotypes, respectively. We recovered and characterized 243 complete HPV genomes from 153 samples spanning 40 different genotypes. According to phylogenetic analysis and pairwise distance, we identified novel lineages and sublineages of four high-risk and 16 low-risk genotypes. In total, 17 novel lineages and 14 novel sublineages were proposed, including novel lineages of HPV45, HPV52, HPV66 and a novel sublineage of HPV59. Our study provides important genomic insights on HPV types and lineages, where few complete genomes were publicly available.