This study aimed to examine correlates of lifetime and past-year HIV testing among men who have sex with men (MSM) in Japan. A unique, anonymous online self-report survey was conducted in 2015. A total of 776 participants completed the survey and answered questions on sociodemographic information, HIV-testing experience, history of syphilis, experience talking about HIV, recognition of AIDS-related community-based organization (CBO) materials, and sex behaviors. HIV-testing experience and related factors were assessed for two groups: regional cities and Tokyo and Osaka. A Poisson regression analysis revealed that higher lifetime HIV testing was associated with older age, previous syphilis diagnosis, and experience talking about HIV. Moreover, higher HIV testing in the past year was associated with experience talking about HIV with friends and recognition of HIV-related CBO materials. Increased dissemination of HIV-related information provided by CBOs may, therefore, be an effective prevention policy intervention targeted at Japanese MSM to promote regular testing and maintain their interest in HIV issues.