INTRODUCTION: As countries approach the UNAIDS 95-95-95 targets, there is a need for innovative and cost-saving HIV testing approaches that can increase testing coverage in hard-to-reach populations. The HIV Self-Testing Africa-Initiative distributed HIV self-test (HIVST) kits using unincentivised HIV testing counsellors across 31 public facilities in Malawi, South Africa, Zambia and Zimbabwe. HIVST was distributed either through secondary (partner's use) distribution alone or primary (own use) and secondary distribution approaches. METHODS: We evaluated the costs of adding HIVST to existing HIV testing from the providers' perspective in the 31 public health facilities across the four countries between 2018 and 2019. We combined expenditure analysis and bottom-up costing approaches. We also carried out time-and-motion studies on the counsellors to estimate the human resource costs of introducing and demonstrating how to use HIVST for primary and secondary use. RESULTS: A total of 41 720 kits were distributed during the analysis period, ranging from 1254 in Zimbabwe to 27 678 in Zambia. The cost per kit distributed through the primary distribution approach was $4.27 in Zambia and $9.24 in Zimbabwe. The cost per kit distributed through the secondary distribution approach ranged from $6.46 in Zambia to $13.42 in South Africa, with a wider variation in the average cost at facility-level. From the time-and-motion observations, the counsellors spent between 20% and 44% of the observed workday on HIVST. Overall, personnel and test kit costs were the main cost drivers. CONCLUSION: The average costs of distributing HIVST kits were comparable across the four countries in our analysis despite wide cost variability within countries. We recommend context-specific exploration of potential efficiency gains from these facility-level cost variations and demand creation activities to ensure continued affordability at scale.