We evaluated the frequency of HIV testing across the Department of Veterans Affairs (VA), the largest provider of HIV care in the United States. An electronic survey was used to determine the volume and location of HIV screening, confirmatory testing, rapid testing and laboratory consent policies in VA medical centers between October 1, 2005, and September 30, 2006. One hundred thirty-five VA laboratories reported that 112,033 HIV screening tests were performed (81% outpatients vs. 19% inpatients, p<.0001). Overall HIV prevalence was 1.49% (1.62% in inpatients vs. 1.46% in outpatients, p=N.S., range=0.2-3.8%). Rapid testing was available in 67% of facilities, 60% of which took place in the clinical laboratory. Sixty-four percent of labs required a copy of the informed consent in order to perform testing. We estimate that fewer than 10% of VA inpatients and fewer than 5% of VA outpatients were tested for HIV during the survey period. Substantial opportunities for increasing routine HIV testing exist in this population.