Few studies have examined the personal and social consequences of stigma associated with HIV infection in Russia, a country with one of the most rapidly advancing HIV epidemics globally. By May 2005, Samara Oblast, Russia had 24,022 notified seropositive individuals. Focus-group discussions with randomly sampled seropositive and seronegative individuals, matched by age, gender and education were selected from the general population and used to provide an informal forum for discussion of attitudes to HIV and potentially stigmatizing behavior. The results demonstrated that the perception that HIV was associated with immoral behaviour underpinned stigma. Discriminating attitudes are strongly associated with misperceptions regarding transmission and frequent over-estimation of risks from casual contact. The general population was unforgiving to those who had become infected sexually or through drug use. Infection through a medical procedure or from an assault was perceived as a likely route of infection. Knowledge of population attitudes and perceptions, as well as those who are HIV-positive, is critical for successful interventions and to encourage people to come forward for HIV testing. This research offers insights into the distance that needs to be traveled if stigma is to be addressed in wider efforts to control HIV in Russia.