Efforts to eliminate the HIV epidemic will require increased HIV testing rates among high-risk populations. To inform the design of HIV testing interventions, a discrete choice experiment (DCE) with six policy-relevant attributes of HIV testing options elicited the testing preferences of 300 female barworkers and 440 male Kilimanjaro mountain porters in northern Tanzania. Surveys were administered between September 2017 and July 2018. Participants were asked to complete 12 choice tasks, each involving first- and second-best choices from 3 testing options. DCE responses were analyzed using a random effects latent class logit (RELCL) model, in which the latent classes summarize common participant preference profiles, and the random effects capture additional individual-level preference heterogeneity with respect to three attribute domains: (a) privacy and confidentiality (testing venue, pre-test counseling, partner notification); (b) invasiveness and perceived accuracy (method for obtaining the sample for the HIV test); and (c) accessibility and value (testing availability, additional services provided). The Bayesian Information Criterion indicated the best model fit for a model with 8 preference classes, with class sizes ranging from 6% to 19% of participants. Substantial preference heterogeneity was observed, both between and within latent classes, with 12 of 16 attribute levels having positive and negative coefficients across classes, and all three random effects contributing significantly to participants’ choices. The findings may help identify combinations of testing options that match the distribution of HIV testing preferences among high-risk populations; the methods may be used to systematically design heterogeneity-focused interventions using stated preference methods.