Human papillomavirus type 16 (HPV-16) genotype variants have been the subject of several investigations, but study participants have rarely been sampled more than once. In this study, among a cohort of human immunodeficiency virus (HIV)-infected adults, HPV-16 variants were investigated in samples collected concurrently from the anus and cervix, as well as in serial samples collected from the same anatomical site at 12-month intervals. HPV-16 variants in stored extracts of cervical and anal samples were determined from subjects with multiple visits and at least one sample positive for HPV-16. Seven polymorphic nucleotide positions within the E6 region were analysed by pyrosequencing to determine genotype variants. Of 364 samples examined, 176 anal and 39 cervical swabs from 84 different subjects yielded unequivocal sequences of eight major HPV-16 variants. Eight samples contained probable novel HPV-16 variants and in one sample two variants were detected. In eight out of 29 (27.6%) anal-cervical sample pairs positive for HPV-16, discordant variants were found. From 57 anal and nine cervical sample series of HPV-16-positive samples, a change in HPV-16 variant status over time was seen in nine (13.6%) instances (seven anal and two cervical) from eight different participants. Changes in HPV-16 variants in HIV-infected adults were seen most frequently when different anatomical sites were sampled, but were also observed over time.