Evidence suggests that treating sexually transmitted infections (STIs) amongst female sex workers (FSWs) is a cost-effective strategy to reduce the spread of HIV/AIDS. Senegal is the only African country where sex work is regulated by a public health policy which aims to monitor and routinely treat STIs. The law requires FSWs to be at least 21 years old, register with a health centre and the police, carry an up-to-date registration booklet, attend monthly health check-ups, and test negative for STIs. Despite health and legal benefits of registration, 80% of FSWs in Senegal are not registered. Hence, the potential health benefits of the policy have not materialised. To understand why FSWs do not want to register and to define policy changes that would increase the registration rate of FSWs in Senegal, we designed and implemented a discrete choice experiment (DCE) completed by 241 registered and 273 non-registered FSWs. Participants made choices between a series of hypothetical but realistic registration policy changes. Conditional logit models were used to analyse the DCE data. The results highlighted that confidentiality at the health facility was an important element, registered and non-registered FWs were respectively 26.0 percentage points (pp) and 22.1 pp more likely to prefer a policy that guaranteed confidentiality at the health centre. Similarly, both groups preferred a policy where their health record was only held at the health centre and not with the police. Several interventions to increase FSW registration rate and improve their wellbeing may be implemented without modifying the law. For example, the introduction of psychosocial support in the registration policy package, replacing the registration booklet by a QR code, the use of electronic medical files and the integration of FSWs routine visits with maternal health appointments to increase confidentiality have the potential to encourage registration of FSWs.