BACKGROUND: In public health HIV treatment programs in Africa, long-term retention remains a challenge. A number of improvement strategies exist (e.g., bring services closer to home, reduce visit frequency, expand hours of clinic operation, improve provider attitude), but implementers lack data about which to prioritize when resource constraints preclude implementing all. We used a discrete choice experiment (DCE) to quantify preferences for a number of potential clinic improvements to enhance retention. METHODS AND FINDINGS: We sought a random sample of HIV patients who were lost to follow-up (defined as >90 days late for their last scheduled appointment) from treatment facilities in Lusaka Province, Zambia. Among those contacted, we asked patients to choose between 2 hypothetical clinics in which the following 5 attributes of those facilities were varied: waiting time at the clinic (1, 3, or 5 hours), distance from residence to clinic (5, 10, or 20 km), ART supply given at each refill (1, 3, or 5 months), hours of operation (morning only, morning and afternoon, or morning and Saturday), and staff attitude ("rude" or "nice"). We used mixed-effects logistic regression to estimate relative utility (i.e., preference) for each attribute level. We calculated how much additional waiting time or travel distance patients were willing to accept in order to obtain other desired features of care. Between December 9, 2015 and May 31, 2016, we offered the survey to 385 patients, and 280 participated (average age 35; 60% female). Patients exhibited a strong preference for nice as opposed to rude providers (relative utility of 2.66; 95% CI 1.9-3.42; p < 0.001). In a standard willingness to wait or willingness to travel analysis, patients were willing to wait 19 hours more or travel 45 km farther to see nice rather than rude providers. An alternative analysis, in which trade-offs were constrained to values actually posed to patients in the experiment, suggested that patients were willing to accept a facility located 10 km from home (as opposed to 5) that required 5 hours of waiting per visit (as opposed to 1 hour) and that dispensed 3 months of medications (instead of 5) in order to access nice (as opposed to rude) providers. This study was limited by the fact that attributes included in the experiment may not have captured additional important determinants of preference. CONCLUSIONS: In this study, patients were willing to expend considerable time and effort as well as accept substantial inconvenience in order to access providers with a nice attitude. In addition to service delivery redesign (e.g., differentiated service delivery models), current improvement strategies should also prioritize improving provider attitude and promoting patient centeredness-an area of limited policy attention to date.