This study determined the overall prevalence of HIV testing within a community sample of heterosexual men and women at high risk for HIV infection, and analysed the gender-specific individual- and structural-level barriers and facilitators to testing. Data were collected through 1,643 personal interviews conducted in Philadelphia between 1999 and 2000. Overall, 79.4% of participants had ever taken an HIV test; women were significantly more likely to have tested than were men. Among the individual-level factors we examined, very few, including sexual and drug-using risk behaviours, were significantly associated with an increased likelihood of ever being tested for HIV. Structural-level factors were important correlates of HIV testing for both women and men. Results of this study indicate that there are gender-based similarities and differences in the correlates of testing, and that efforts to increase HIV testing must consider how structural factors, including access to health care, may deter or facilitate opportunities for HIV testing. In particular, efforts to improve the uptake of HIV testing by heterosexual men at high risk should focus on improving men's access to, and utilization of, routine health care.