Risky drug- and sex-related behaviors put criminal offenders at high risk for HIV. Intervening with this population under supervision can potentially reduce risk. This study reports a randomized trial that examines the efficacy of brief negotiation interviewing (BNI) compared to usual education activities. BNI is a computerized, self-directed intervention that combines a short structured interview with a brief counseling session. The study examined whether BNI could decrease HIV risks and increase testing for HIV in a cohort of criminal-justice-involved clients. The trial randomly assigned 212 participants to experimental (108) and control (104) conditions. Interview data were collected at baseline and at 2-month follow-up. Results indicate that the BNI intervention group had a significantly higher rate of HIV testing and was more likely to consider behavioral changes.