BACKGROUND: Despite high HIV prevalence rates among most-at-risk groups, utilisation of HIV testing, treatment and care services was relatively low in Karnataka prior to 2008. The authors aimed to understand the barriers to and identify potential solutions for improving HIV service utilisation. METHODS: Focus group discussions were carried out among homogeneous groups of female sex workers, men who have sex with men and transgenders, and programme peer educators in six districts across Karnataka in March and April 2008. RESULTS: 26 focus group discussions were conducted, involving 302 participants. Participants had good knowledge about HIV and HIV voluntary counselling and testing (VCT) services, but awareness of other HIV services was low. The fear of the psychological impact of a positive HIV test result and the perceived repercussions of being seen accessing HIV services were key personal and interpersonal barriers to HIV service utilisation. Previous experiences of discrimination at government healthcare services, coupled with discriminatory attitudes and behaviours by VCT staff, were key structural barriers to VCT service uptake among those who had not been HIV tested. Among those who had used government-managed prevention of parent to child transmission and antiretroviral treatment services, poor physical facilities, long waiting times, lack of available treatment, the need to give bribes to receive care and discriminatory attitudes of healthcare staff presented additional structural barriers. CONCLUSIONS: Embedding some HIV care services within existing programmes for vulnerable populations, as well as improving service quality at government facilities, are suggested to help overcome the multiple barriers to service utilisation. Increasing the uptake of HIV testing, treatment and care services is key to improving the quality and longevity of the lives of HIV-infected individuals.