Screening everyone for HIV at least once is estimated to be cost-effective. Screening in health care settings is recommended to help achieve that goal. Health care settings often encounter the same patient repeatedly, and it is unknown if limited resources are better allocated to conduct repeat screening, or to screen patients not yet tested. We reviewed data for a targeted ED based HIV screening program for 2003-2007. The role of prior testing history as a predictor of undiagnosed HIV positivity was assessed using a negative binomial model adjusted for demographics and risk behaviors. HIV testing was provided to 8,450 unique patients. There were 5,781 (70%) self-reporting a prior HIV test. Compared with patients reporting no prior test, the relative risk of HIV positivity for those reporting a test within the prior year was 0.90 (95%CI 0.48-1.66), and for those reporting a prior test more than a year previously the relative risk was 0.91 (95%CI 0.48-1.73). Among patients testing positive, those who did not report a prior test had a median CD4 count that was 228 cells/mm3 lower than those with a prior test (CI95 of the difference in medians 20-436 cells/mm3). Diagnosis of prevalent HIV among those who are at risk but have never been tested should be a priority. However, repeat screening of target populations for incident infection remains important and results in earlier diagnosis. Recent self-reported testing history is not associated with undiagnosed positivity among targeted patients irrespective of the timing of the prior test.