African-American men who have sex with men (AA MSM) have been disproportionately infected with and affected by HIV and other STIs in San Francisco and the USA. The true scope and scale of the HIV epidemic in this population has not been quantified, in part because the size of this population remains unknown. We used the successive sampling population size estimation (SS-PSE) method, a new Bayesian approach to population size estimation that incorporates network size data routinely collected in respondent-driven sampling (RDS) studies, to estimate the number of AA MSM in San Francisco. This method was applied to data from a 2009 RDS study of AA MSM. An estimate from a separate study of local AA MSM was used to model the prior distribution of the population size. Two-hundred and fifty-six AA MSM were included in the RDS survey. The estimated population size was 4917 (95% CI 1267–28,771), using a flat prior estimated 1882 (95% CI 919–2463) as a lower acceptable bound, and a large prior estimated 6762 (95% CI 1994–13,863) as an acceptable upper bound. Point estimates from the SS-PSE were consistent with estimates from multiplier methods using external data. The SS-PSE method is easily integrated into RDS studies and therefore provides a simple and appealing tool to rapidly produce estimates of the size of key populations otherwise difficult to reach and enumerate.