Current HIV policies in Tanzania have adopted the three long-term impact results of zero new infections, zero HIV deaths and zero stigma and discrimination. Strategies to reach these results include scaling-up HIV Testing and Counselling (HTC); Preventing Mother-To-Child Transmission (PMTCT); and strengthening Care and Treatment Clinic (CTC) services. Previous studies showed that HIV policy and guideline recommendations were not always implemented in rural South Tanzania. This study aims to identify the determinants of HIV guideline implementation. A qualitative study of 23 semi-structured interviews with facility in-charges; healthcare workers; district, regional and national HIV coordinators was conducted. Five health facilities were purposively selected by level, ownership and proximity to district headquarters. Interviews were analysed according to Fleuren's five determinants of innovation uptake related to: strategies used in guideline development and dissemination; guideline characteristics; the guideline implementing organization; guideline users; and the socio-cultural and regulatory context. None of the facilities had the HTC national guideline document. Non-involvement of providers in revisions and weak planning for guideline dissemination impeded their implementation. Lengthy guidelines and those written in English were under-used, and activities perceived to be complicated, like WHO-staging, were avoided. Availability of staff and lack of supplies like test kits and medication impeded implementation. Collaboration between facilities enhanced implementation, as did peer-support among providers. Provider characteristics including education level, knowledge of, and commitment to the guideline influenced implementation. According to providers, determinants of clients' service use included gender norms, stigma, trust and perceived benefits. The regulatory context prohibited private hospitals from buying HIV supplies. Being tools for bringing policies to practice, national guidelines are crucial in the efforts towards the three zeros. Strategies to improve providers' adherence to guidelines should include development of clearer guideline dissemination plans, strengthening of the health system, and possibly addressing of provider-perceived patient-level barriers to utilizing HIV services.