BACKGROUND: Voluntary counselling and testing (VCT) for HIV first evolved in Western settings, with one aim being to promote behaviours which lower the risk of onward transmission or acquisition of HIV. However, although quantitative studies have shown that the impact of VCT on sexual behaviour change has been limited in African settings, there is a lack of qualitative research exploring perceptions of HIV prevention counselling messages, particularly among clients testing HIV-negative. We conducted a qualitative study to explore healthcare worker, community and both HIV-negative and HIV-positive clients' perceptions of HIV prevention counselling messages in rural Tanzania. METHODS: This study was carried out within the context of an ongoing community HIV cohort study in Kisesa, northwest Tanzania. Nine group sessions incorporating participatory learning and action (PLA) activities were conducted in order to gain general community perspectives of HIV testing and counselling (HTC) services. Thirty in-depth interviews (IDIs) with HIV-negative and HIV-positive service users explored individual perceptions of HIV prevention counselling messages, while five IDIs were carried out with nurses or counsellors offering HTC in order to explore provider perspectives. RESULTS: Two key themes revolving around socio-cultural and contextual factors emerged in understanding responses to HIV prevention counselling messages. The first included constraints to client-counsellor interactions, which were impeded as a result of difficulties discussing private sexual behaviours during counselling sessions, a hierarchical relationship between healthcare providers and clients, insufficient levels of training and support for counsellors, and client concerns about confidentiality. The second theme related to imbalanced gender-power dynamics, which constrained the extent to which women felt able to control their HIV-related risk. CONCLUSION: Within the broader social context of a rural African setting, HIV prevention counselling based on a Western model of individual-level agency seems unlikely to make a significant contribution to sexual behaviour change until there is greater recognition by counsellors of the ways in which power dynamics within many relationships influence behaviour change. More culturally relevant counselling strategies and messages and infrastructural improvements such as additional training for counsellors and counselling rooms which ensure privacy and confidentiality, may lead to better outcomes in terms of sexual risk reduction.