Despite recommendations for voluntary HIV screening, few medicalcentres have implemented screening programmes. The objective of the study was to determine whether an intervention with computer-based reminders and feedback would increase screening for HIV in a Department of Veterans Affairs (VA) health-care system. The design of the study was a randomized controlled trial at five primary care clinics at the VA Palo Alto Health Care System. All primary care providers were eligible to participate in the study. The study intervention was computer-based reminders to either assess HIV risk behaviours or to offer HIV testing; feedback on adherence to reminders was provided. The main outcome measure was the difference in HIV testing rates between intervention and control group providers. The control group providers tested 1.0% (n = 67) and 1.4% (n = 106) of patients in the preintervention and intervention period, respectively; intervention providers tested 1.8% (n = 98) and 1.9% (n = 114), respectively (P = 0.75).In our random sample of 753 untested patients, 204 (27%) had documented risk behaviours. Providers were more likely to adhere to reminders to test rather than with reminders to perform risk assessment (11% versus 5%, P < 0.01). Sixty-one percent of providers felt that lack of time prevented risk assessment. In conclusion, in primary care clinics in our setting, HIV testing rates were low. Providers were unaware of the high rates of risky behaviour in their patient population and perceived important barriers to testing. Low-intensity clinical reminders and feedback did not increase rates of screening.