This study assessed the correlates of recent HIV testing and HIV/AIDS-related stigmatizing and discriminatory attitudes among men who have sex with men (MSM) in Beijing, China. A cross-sectional study probed demographics, sexual and drug use behaviors, HIV testing, and prevention services. Of 500 participants, 39.3% recently received a test for HIV. Recent testing was independently associated with expressing lower levels of HIV/AIDS-related stigmatizing and discriminatory attitudes, more male sex partners, no female sexual partners and knowing HIV status of their last male partner. Expressing lower levels of HIV/AIDS-related stigmatizing and discriminatory attitudes was independently associated with recent testing, younger age, and knowing HIV status of their last male partner. This study revealed that HIV/AIDS-related stigmatizing and discriminatory attitudes were common and inversely associated with recent HIV testing. Low levels of testing highlighted the urgent needs to reduce HIV/AIDS-related stigma and discrimination and expand HIV testing among MSM in Beijing.