Cognitive processing models of risky sexual behaviour have proliferated in the two decades since the first reporting of HIV/AIDS, but far less attention has been paid to individual and group representations of the epidemic and the relationship between these representations and reported sexual behaviours. In this study, 494 business people and medics from Estonia, Georgia, Hungary, Poland and Russia sorted free associations around HIV/AIDS in a matrix completion task. Exploratory factor and multidimensional scaling analyses revealed two main dimensions (labelled 'Sex' and 'Deadly disease'), with significant cultural and gender variations along both dimension scores. Possible explanations for these results are discussed in the light of growing concerns over the spread of the epidemic in this region.