OBJECTIVES: This study estimates the costs of community-based HIV testing services (HTS) in Lesotho and assesses the potential efficiency gains achieved by adding HIV self-testing (HIVST) and then self-testing booths. DESIGN: Micro-costing analysis using longitudinal data from a real-world intervention. METHODS: We collected data prospectively on provider's costs and programmatic outcomes over three time periods of approximately 8 months each, between May 2017 and April 2019. The scope of services was extended during each period as follows: HTS only, HTS and HIVST, HTS and HIVST with individual HIVST booths wherein clients were encouraged to self-test on-site followed by on-site confirmative testing for those with reactive self-test. For each implementation period, we estimated the full financial and economic implementation costs, the incremental costs of adding HIVST onto conventional HTS and the cost per HIV positive case identified. RESULTS: Costs per HIV-positive case identified increased between period 1 (US$956) and period 2 (US$1249) then dropped in period 3 (US$813). Full versus incremental cost analyses resulted in large differences in the magnitude of costs, attributable to methods rather than resource use: for example, in period 3, the average full and incremental cost estimates for HTS were US$34.3 and US$23.5 per person tested, and for HIVST were US$37.7 and US$14.0 per kit provided, respectively. CONCLUSION: In Lesotho, adding HIVST to community-based HTS improves its overall affordability for HIV-positive case finding. The reporting of both full and incremental cost estimates increase transparency for use in priority setting, budgeting and financial planning for scale-up.