Background. Anal cancer rates are higher for human immunodeficiency virus (HIV)-infected adults than for uninfected adults. Limited published data exist characterizing the incidence of precursor lesions detected by anal cytology. Methods. The Study to Understand the Natural History of HIV/AIDS in the Era of Effective Therapy was a prospective cohort of 700 HIV-infected participants in 4 US cities. At baseline and annually thereafter, each participant completed a behavioral questionnaire, and healthcare professionals collected anorectal swabs for cytologic examination and human papillomavirus (HPV) detection and genotyping. Results. Among 243 participants with negative baseline results of anal cytology, 37% developed abnormal cytology findings (incidence rate, 13.9 cases/100 person-years of follow-up; 95% confidence interval [CI], 11.3-16.9) over a median follow-up duration of 2.1 years. Rates among men having sex with men, among women, and among men having sex with women were 17.9 cases/person-years of follow-up (95% CI, 13.9-22.7), 9.4 cases/person-years of follow-up (95% CI, 5.6-14.9), and 8.9 cases/person-years of follow-up (95% CI, 4.8-15.6), respectively. In multivariable analysis, the number of persistent high-risk HPV types (adjusted hazard ratio [aHR], 1.17; 95% CI, 1.01-1.36), persistent high-risk HPV types except 16 or 18 (aHR, 2.46; 95% CI, 1.31-4.60), and persistent types 16 or 18 (aHR, 3.90; 95% CI, 1.78-8.54) remained associated with incident abnormalities. Conclusions. The incidence of abnormal anal cytology findings was high and more likely to develop among persons with persistent high-risk HPV.