BACKGROUND: With new testing technologies, task-shifting and rapid scale-up of HIV testing services in high HIV prevalence countries, assuring quality of HIV testing is paramount. This study aimed to explore various cadres of providers' experiences in providing HIV testing services and their understanding of elements that impact on quality of service in Zambia. METHODS: Sixteen in-depth interviews and two focus group discussions were conducted with HIV testing service providers including lay counselors, nurses and laboratory personnel at purposively selected HIV testing sites at a national reference hospital in Lusaka. Qualitative content analysis was adopted for data analysis. RESULTS: Lay counselors and nurses reported confidentiality and privacy to be greatly compromised due to limited space in both in- and out-patient settings. Difficulties in upholding consent were reported in provider-initiated testing in in-patient settings. The providers identified non-adherence to testing procedures, high workload and inadequate training and supervision as key elements impacting on quality of testing. Difficulties related to testing varied by sub-groups of providers: lay counselors, in finger pricking and obtaining adequate volumes of specimen; non-laboratory providers in general, in interpreting invalid, false-negative and false-positive results. The providers had been participating in a recently established national HIV quality assurance program, i.e. proficiency testing, but rarely received site supervisory visits. CONCLUSION: Task-shifting coupled with policy shifts in service provision has seriously challenged HIV testing quality, protection of confidentiality and the process of informed consent. Ways to better protect confidentiality and informed consent need careful attention. Training, supervision and quality assurance need strengthening tailored to the needs of the different cadres of providers.