At the end of 2013, the Government of Uganda issued guidance recommending provision of Anti-Retroviral Treatment (ART) to HIV-positive people in key populations, including female sex workers, regardless of CD4 cell count. We describe the implementation of this new guidance in a clinic serving women at high risk of HIV infection in Kampala. Between July and December 2015, we conducted repeat in-depth interviews with 15 women attending the clinic after the change in guidelines, to explore their perceptions regarding prompt ART initiation. The sample included some women who were HIV-negative and women who had both started and deferred ART. We conducted a data-led thematic analysis of the material from the interviews. A total of 257 of 445 eligible women had started ART; others were undecided or had not returned to the clinic after receiving the new information. Participants recounted varying experiences with the provision of prompt treatment. At an individual level, a history of treatment for opportunistic infections and other illnesses, coupled with relatively poor health, encouraged some to initiate ART promptly. However, knowledge of friends/relatives already on ART who had experienced side effects caused others to delay starting, fearing the same experience for themselves. A number of women questioned why they should start treatment when they were not sick. Situational factors such as work and residence (with many sharing single rooms) caused discomfort among newly diagnosed women who feared disclosure and stigma that would result from taking ART when they were not ill. Alcohol consumption and irregular working hours affected perceptions of future adherence, making prompt ART harder to embrace for some. Our findings show the challenges that influence the delay of treatment initiation, and/or the decision to defer receiving information on ART, with implications for the success of the test and treat programmes and guidelines.