Abstract: Background: In Sub-Saharan Africa where HIV disproportionately affects women, heterosexual male sex workers (HMSW) and their female clients are at risk of acquiring or transmitting HIV and other STIs. However, few studies have described HIV and STI risk among HMSW. We aimed to assess and compare recent HIV and syphilis screening practices among HMSW and female sex workers (FSW) in Uganda. Methods: Between August and December 2019, we conducted a cross-sectional study among 100 HMSW and 240 female sex workers (FSW). Participants were enrolled through snowball sampling, and an interviewer-administered questionnaire used to collect data on HIV and syphilis testing in the prior 12 and 6 months respectively. Integrated change model constructs were used to assess intentions, attitudes, social influences, norms and self-efficacy of 3-monthly Syphilis and 6-monthly HIV testing. Predictors of HIV and syphilis recent testing behaviors were estimated using negative binomial regression. Results: We enrolled 340 sex workers of whom 100 (29%) were HMSW. The median age was 27 years [interquartile range (IQR) 25–30] for HMSW and 26 years [IQR], (23–29) for FSW. The median duration of sex work was 36 and 30 months for HMSW and FSW, respectively. HMSW were significantly less likely than FSW to have tested for HIV in the prior 12 months (50% vs. 86%; p = 0.001). For MSW, non-testing for HIV was associated with higher education [adjusted prevalence ratio (aPR) 1.66; 95% confidence interval (CI) 1.09–2.50], poor intention to seek HIV testing (aPR 1.64; 95% CI 1.35–2.04), perception that 6-monthly HIV testing was not normative (aPR 1.33; 95% CI 1.09–1.67) and low self-efficacy (aPR 1.41; 95% CI 1.12–1.79). Not testing for syphilis was associated with low intention to seek testing (aPR 3.13; 95% CI 2.13–4.55), low self-efficacy (aPR 2.56; 95% CI 1.35–4.76), negative testing attitudes (aPR 2.33; 95% CI 1.64–3.33), and perception that regular testing was not normative (aPR 1.59; 95% CI 1.14–2.22). Conclusions: Non-testing for HIV and syphilis was common among HMSW relative to FSW. Future studies should evaluate strategies to increase testing uptake for this neglected sub-population of sex workers.