Background Regular testing of individuals at higher-risk of HIV is central to current prevention strategies. The aim of the present study was to examine the extent to which confidence in one’s perceived ability to undertake various aspects of HIV testing and self-testing (self-efficacy) affected HIV testing outcomes. We assessed factors, including self-efficacy, associated with HIV testing frequency and the likelihood to self-test among gay and bisexual men (GBM). Methods: Participants were HIV-negative GBM at an increased risk of HIV (more than five partners or condomless anal intercourse in the previous 3 months) enrolled in a randomised controlled trial of HIV self-testing. The baseline questionnaire captured data regarding sociodemographic characteristics, HIV and/or sexually transmissible infection testing history, sexual behaviour, beliefs and attitudes towards HIV and eight items capturing confidence in HIV testing ability that were combined as a single broad measure of HIV testing self-efficacy (α = 0.81). Factors associated with three or more HIV tests in the past year and the likelihood of self-testing in the future were determined using logistic regression. Results: Of 354 GBM, 34% reported three or more HIV tests in the past year, and 64% reported being ‘very likely’ to self-test. Factors independently associated with three or more HIV tests in the past year were: higher self-efficacy (adjusted odds ratio (aOR) 1.08 per unit increase; 95% confidence interval (CI) 1.02–1.14; P = 0.004); >10 male partners in the past 6 months (aOR 1.79; 95% CI 1.05–3.04; P = 0.031) and higher optimism regarding the effects of HIV treatments on HIV transmission (aOR 1.14; 95% CI 1.00–1.29; P = 0.044). Only higher self-efficacy was independently associated with reporting a greater likelihood to self-test in the future (aOR 1.10; 95% CI 1.05–1.15; P < 0.001). Conclusions: Improving self-efficacy by enhancing GBM’s knowledge and experience may lead to higher testing frequency. The self-efficacy measure used in the present study could be useful in identifying GBM likely to face difficulties with HIV testing and self-testing.