Objective. The aim of the study was to determine the prevalence of HIV-associated oral mucosal melanin hyperpigmentation (HIV-OMH) in a specific population of HIV-seropositive South Africans and to analyse the associations between HIV-OMH clinical features and the demographic and immunological characteristics of the study cohort. Material and Methods. This cross-sectional study included 200 HIV-seropositive Black subjects. The collected data comprised age, gender, CD4+ T cell count, viral load, systemic disease, medications, oral site affected by HIV-OMH, extent (localized or generalized), intensity of the pigmentation (dark or light), and smoking and snuff use. Results. Overall, 18.5% of the study cohort had HIV-OMH. Twenty-two and a half percent had OMH that could not with confidence be attributed to HIV infection, and 59% did not have any OMH. There was a significant but weak association between smoking and the presence of HIV-OMH. Conclusions. The prevalence of HIV-OMH in the study population was 18.5%, the gingiva being the most commonly affected site. It appears that the CD4+ T cell count does not play any role in the biopathology of HIV-OMH.