Background: Ten million Americans enter jails annually. The objective was to evaluate new CDC guidelines for routine opt-out HIV testing and examine the optimal time to implement routine opt-out HIV testing among newly incarcerated jail detainees. Methods: This prospective, controlled trial of routine opt-out HIV testing was conducted among 323 newly incarcerated female inmates in Connecticut's only women's jail. 323 sequential entrants to the women's jail over a five week period in August and September 2007 were assigned to be offered routine opt-out HIV testing at one of three points after incarceration: immediate (same day, n = 108), early (next day, n = 108), or delayed (7 days, n = 107). The primary outcome was the proportion of women in each group consenting to testing. Results: Routine opt-out HIV testing was significantly highest (73%) among the early testing group compared to 55% for immediate and 50% for 7 days post-entry groups. Other factors significantly (p = 0.01) associated with being HIV tested were younger age and low likelihood of early release from jail based on bond value or type of charge for which women were arrested. Conclusions: In this correctional facility, routine opt-out HIV testing in a jail setting was feasible, with highest rates of testing if performed the day after incarceration. Lower testing rates were seen with immediate testing, where there is a high prevalence of inability or unwillingness to test, and with delayed testing, where attrition from jail increases with each passing day.