Estimating the size of populations most affected by HIV such as men who have sex with men (MSM) though crucial for structuring responses to the epidemic presents significant challenges, especially in a developing society. Using capture-recapture methodology, the size of MSM-SW in Nigeria was estimated in three major cities (Lagos, Kano and Port Harcourt) between July and December 2009. Following interviews with key informants, locations and times when MSM-SW were available to male clients were mapped and designated as “hotspots”. Counts were conducted on two consecutive weekends. Population estimates were computed using a standardized Lincoln formula. Fifty six hotspots were identified in Kano, 38 in Lagos and 42 in Port Harcourt. On a given weekend night, Port Harcourt had the largest estimated population of MSM sex workers, 723 (95%CI: 594-892) followed by Lagos state with 620 (95%CI: 517-724) and Kano state with 353 (95%CI: 332-373). This study documents a large population of MSM-SW in 3 Nigerian cities where higher HIV prevalence among MSM compared to the general population has been documented. Research and programming are needed to better understand and address the health vulnerabilities that MSM-SW and their clients face.