The District of Columbia launched a routine HIV testing initiative in 2006. We examined HIV testing behaviors among heterosexuals at risk for HIV over time using CDC National HIV Behavioral Surveillance data from Washington, DC for the heterosexual cycles from 2006 to 2007 (Cycle 1) and 2010 (Cycle 2). Past year and past 2-year HIV testing across study cycles were compared using Chi square tests. Weighted multivariable logistic regression identified correlates of past year testing. The majority of participants across both cycles were black and female. Cycle 1 participants were significantly more likely to have ≥4 partners in the past year, casual sex partners, and have anal sex at last sexual encounter (p < 0.05). Lifetime testing was high, and individuals from Cycle 2 versus Cycle 1 were more likely to have been tested in the past 2 years. There were no significant differences in past year testing or being offered the HIV test at last health care visit by cycle. Independent correlates of past year testing were seeing a health care provider in the past year and using condoms at last vaginal sex. In conclusion, although past year testing did not differ between the two data collection years, the proportion of heterosexuals testing in the past 2 years was higher in Cycle 2 versus Cycle 1, suggesting successful expansion of HIV testing between the two time periods.