In China, men who have sex with men (MSM) are at high risk for HIV. However, little is known about their HIV testing behavior. From September 2001 to January 2002, we recruited 482 men through social networks and MSM venues. We conducted HIV testing and counseling, and anonymous, standardized face-to-face interviews. Eighty-two percent of participants had never tested for HIV before the study. The most common reasons for not testing were perceived low risk of HIV infection (72%), not knowing the location of test sites (56%), fear of positive test results (54%), fear of people learning about his homosexuality (47%), and fear of breach of confidentiality about test results (47%). We identified five statistically significant independent correlates of having been tested for HIV: being older, having a college degree, being more "out" (disclosing MSM activities to people), being recruited through social networks, and having a lifetime history of sexually transmitted diseases. Of 15 participants (3.1%) who tested positive for HIV in our study, 14 (93%) did not know their status before being tested in the study. The prevalence of HIV testing among MSM in Beijing is low; almost all HIV-positive men in our study were unaware of their infection. Our findings suggest an urgent need to promote HIV testing among MSM in Beijing.