In many countries around the world sex work is criminalised and its regulatory control is therefore often in the hands of the police. In addition to the impact of this criminalised legal environment, much literature describes the negative impact that certain police practices can have on the ability of sex workers and the programs that work with sex workers to access essential HIV prevention, treatment, care and support services. This situation has resulted in persistent concentrated HIV epidemics among sex workers in many countries of the world. The need for multi-sector partnerships between police and HIV programs is increasingly recognised in various UN declarations and resolutions yet descriptions of the process or key ingredients required to actually establish and sustain these necessary partnerships between police and sex workers [or the programs that provide essential services to sex workers] are sparse. The paper seeks to establish key considerations and critical processes that are required to foster partnerships that if further investigated and scaled up, could result in an enhanced enabling environment for the provision of essential HIV services for sex workers around the globe. This paper is based on a realist review that investigated isolated examples of partnership formation between law enforcement and HIV programs working with sex workers. This methodology research is designed to work with complex social interventions and is based on the emerging 'realist' approach to evaluation. A realist review methodology was chosen given the paucity of relevant literature in this vein and the authors' familiarity with the grey literature and relationships with experts who work in this sphere. The review found that political and police leadership, civil society strengthening and police reform in relation to HIV, are critical factors and key ingredients in changing the enabling environment in which sex work takes place to ensure that HIV prevention, individual and public health as well as HIV prevention and the promotion of human rights are the number one priority. Further research into this relationship is needed to provide evidence for effective HIV programming with police.