Background Increasing the frequency of HIV testing is crucial for effective HIV prevention and care. The aim of the present study was to determine whether there has been a change in HIV testing among men who have sex with men (MSM) at the South Australia Specialist Sexual Health (SASSH) clinic over the past two decades. Methods: Computerised medical records of MSM who attended the SASSH at their first visit between 1994 and 2015 were used to determine whether HIV testing had changed among MSM. First HIV tests in each calendar year and return tests within 12 months were analysed. Factors associated with recent HIV testing were also examined. Results: There were 24036 HIV tests conducted among 8163 individual MSM over the study period. The proportion of newly registered MSM who reported ever being tested for HIV declined (Ptrend≤0.030), the proportion who reported recent HIV testing did not change (Ptrend≤0.955) and the proportion who have had current HIV testing increased (Ptrend≤0.008). The proportion of MSM who returned to the clinic for HIV testing within 12 months did not change (Ptrend >0.05), with less than 40% of MSM returning for HIV testing. Factors independently associated with recent HIV testing included MSM aged ≥20 years, (odds ratio (OR) 1.79; 95% confidence interval (CI) 1.53-2.10), higher education (OR 1.28; 95% CI 1.12-1.45), non-Caucasian (African OR 1.68; 95% CI 1.30-2.17), having multiple sex partners (OR 1.47; 95% CI 1.29-1.69), having had sex interstate (OR 1.61; 95% CI 1.42-1.82) or overseas (OR 1.53; 95% CI 1.33-1.76) and injecting drug use (OR 1.56; 95% CI 1.29-1.88). Conclusions: HIV testing rate among MSM attending SASSH was suboptimal. New approaches are needed to increase the uptake and early detection of HIV infection among the high-priority MSM population.