Men who purchase sex (MWPS) have long been considered as one of the population groups at risk of HIV transmission. However, while HIV-related interventions have been targeted towards this group, few studies have directly recruited MWPS to measure the impact of such interventions. This study aimed to fill the gap for Indonesia by identifying the level and predictors of condom use and HIV testing among MWPS, to inform prevention strategies. A cross-sectional study was conducted by surveying 200 MWPS in Bali, Indonesia in 2015. A structured questionnaire was administered to collect the data. Self-reported condom use on the occasion of last paid sex was very high (88.5%), while a history of HIV testing was low (8.1%). None of the variables identified in this study were associated with condom use at last paid sex. Men were more likely to report a history of HIV testing if they: perceived themselves to be at high risk of HIV, had a higher level of HIV-related knowledge, reported a history of genital ulcers or urethral discharge in the past 12 months, or were aware that confidential HIV testing was available. Implications and limitations of this study are discussed.