Background: It is common practice for HIV programmes to routinely trace patients who are late for a scheduled clinic visit to ensure continued care engagement. In South Africa, patients who are late for a scheduled visit are identified from clinic registers, and called by telephone up to three times by designated clinic staff, with home visits conducted for those who are unreachable by phone. It is important to understand outcomes among late patients in order to have accurate mortality data, identify defaulters to attempt to re-engage them into care, and have accurate estimates of patients still in care for planning purposes.Objective: We conducted a study to assess whether tracing of HIV patients in clinics in rural north-eastern South Africa was implemented in line with national policies.Methods: Thirty-three person-day of observations took place during multiple visits to eight facilities between October 2017 and January 2018 during which clinic tracing processes were captured. The facility level implementation processes were compared to the intended tracing process and gaps and challenges were identified.Results: Challenges to implementing effective tracing procedures fell into three broad categories: i) facility-level barriers, ii) issues relating to data, documentation and record-keeping, and iii) challenges relating to the roles and responsibilities of the different actors in the tracing cascade.We recommend improving linkages between clinics, improving record-keeping systems, and regular training of community health workers involved in tracing activities. Improved links between clinics would reduce the chance of patients being lost between clinics. Record-keeping systems could be improved through motivating health workers to take ownership of their data and training them on the importance of complete data. Finally, training of community health workers may improve sustained motivation, and improve their ability to respond appropriately to their clients' needs.Conclusions: Substantial investment in data infrastructure and healthcare staff training is needed to improve routine tracing.