Women living with HIV (WLHIV) are at increased risk for human papillomavirus (HPV)-associated anal cancer. Given the “field effect” of HPV pathogenesis, some recommend that anal cancer screening should be limited to WLHIV with prior genital disease. This study aimed to characterize the relationship between anal and genital disease in WLHIV in order to better inform anal cancer screening guidelines. We retrospectively studied 153 WLHIV with biopsy-proven anal high-grade squamous intraepithelial lesions (AHSIL) and long-term evaluable cervical/vaginal/vulvar histopathology. Based on the absence or presence of genital HSIL, subjects were categorized as having isolated AHSIL or multicentric HSIL. Demographics, HIV parameters and cervical/anal HPV status were recorded. Chi-square test was used for bivariate analyses. Of 153 WLHIV with AHSIL, 110 (72%) had isolated AHSIL, while 43 (28%) had multicentric HSIL (28 cervical, 16 vulvar, and 8 vaginal HSIL). The median genital surveillance was 8 years (range 1–27). Cervical HPV16/18 infection was associated with multicentric disease (P = 0.001). Overall, 53% of multicentric cases presented genital HSIL preceding AHSIL with median interval 13 years (range 2–23). Paired anal and cervical high-risk HPV results were available for 60 women within 12 months of AHSIL diagnosis: 30 (50%) had anal infection alone, while 30 (50%) had anal/cervical coinfection by 16/18 (15%), non-16/18 (13%), or different types (22%). In conclusion, WLHIV frequently develop AHSILs without pre-existing genital disease or after long latency following a genital HSIL diagnosis. Our findings support anal cancer screening for WLHIV irrespective of prior genital disease.