BACKGROUND: Successful HIV testing, care and treatment policy implementation is essential for realising the reductions in morbidity and mortality those policies are designed to target. While adoption of new HIV policies is rapid, less is known about the facility-level implementation of new policies and the factors influencing this. METHODS: We assessed implementation of national policies about HIV testing, treatment and retention at health facilities serving two health and demographic surveillance sites (HDSS) (10 in Kyamulibwa, 14 in Rakai). Ugandan Ministry of Health HIV policy documents were reviewed in 2013, and pre-determined indicators were extracted relating to the content and nature of guidance on HIV service provision. Facility-level policy implementation was assessed via a structured questionnaire administered to in-charge staff from each health facility. Implementation of policies was classified as wide (≥75% facilities), partial (26-74% facilities) or minimal (≤25% facilities). Semi-structured interviews were conducted with key informants (policy-makers, implementers, researchers) to identify factors influencing implementation; data were analysed using the Framework Method of thematic analysis. RESULTS: Most policies were widely implemented in both HDSS (free testing, free antiretroviral treatment (ART), WHO first-line regimen as standard, Option B+). Both had notable implementation gaps for policies relating to retention on treatment (availability of nutritional supplements, support groups or isoniazid preventive therapy). Rakai implemented more policies relating to provision of antiretroviral treatment than Kyamulibwa and performed better on quality of care indicators, such as frequency of stock-outs. Factors facilitating implementation were donor investment and support, strong scientific evidence, low policy complexity, phased implementation and effective planning. Limited human resources, infrastructure and health management information systems were perceived as major barriers to effective implementation. CONCLUSIONS: Most HIV policies were widely implemented in the two settings; however, gaps in implementation coverage prevail and the value of ensuring complete coverage of existing policies should be considered against the adoption of new policies in regard to resource needs and health benefits.