Men who have sex with men (MSM) may account for an increasing proportion of China's HIV epidemic, but remain difficult to access for epidemiological studies due to high stigma. We compare the composition of two samples of MSM obtained in Guangzhou, China. The first survey, conducted in 2004, recruited MSM through convenience sampling. The second survey in 2006 used long-chain referral recruitment in the context of respondent-driven sampling. Compared to convenience sampling, the long-chain referral method included higher proportions of subgroups of MSM thought to be at elevated risk for HIV infection and more difficult to reach, including internal migrants and those engaging in commercial sex. Long-chain referral also recruited more MSM who were under 25 years, unemployed, and had lower education. We conclude that long-chain referral recruitment will be more effective in tracking the leading edge of the epidemic among MSM in China than convenience sampling.