The aim of this study was to investigate the factors relating to CD4 level at HIV diagnosis and HIV testing behaviour. Participants were newly diagnosed patients ( n = 654) in Japan from 2000 to 2005. Around 75% of participants were diagnosed at hospital and clinics. Mean CD4 counts at diagnosis through voluntary HIV testing, screening tests and testing due to concomitant sexually transmitted infection (STI) were 368, 336 and 316 cells/μL, respectively. In contrast, the mean CD4 count where testing was due to the presence of HIV-related clinical symptoms was 151 cells/μL ( P < 0.0001). Compared with those diagnosed at their first HIV test, those who had undertaken multiple HIV tests prior to diagnosis showed CD4 counts that increased significantly ( P < 0.0001) in relation to the number of tests undertaken: CD4 count at first test was 232 cells/μL, second test 346 cells/μL and third or additional tests 439 cells/μL. According to our results, HIV testing policy that promotes HIV testing in medical settings and among STI patients is needed to facilitate earlier HIV diagnosis in Japan.