Background: HIV prevalence among female sex workers in Indonesia remains high and large proportions of female sex workers have never been tested for HIV. International research highlights the importance of community-led strategies to increase HIV testing in this population. Little qualitative research has been conducted to address these issues in Indonesia or other Asia-Pacific countries. This paper documents social influences that enhance HIV testing among female sex workers in urban Indonesia. Methods: This was an interpretive qualitative study in Yogyakarta, Denpasar and Bandung. In total, 57 female sex workers participated in 11 focus group discussions, and four participated in individual semi-structured interviews. Deductive and inductive thematic analysis techniques were used to identify narratives of strengths pertaining to uptake of HIV testing. Results: Participants described supportive relationships with peers, community-based organisations and 'bosses'. Participants reported trusted networks with peers within which to share information about HIV testing and receive emotional support. Relationships with community outreach workers facilitated HIV testing through reminders, accompanied visits, and emotional/informational support. Community-based organisations worked with health services to facilitate mobile, community-based testing to overcome employment- and family-related constraints that inhibited women's clinic attendance. 'Bosses' employed a variety of practices to encourage HIV testing among their workers. Conclusions: Relationships, practices and action in community- and workplace-based settings outside formal health service spaces enhanced HIV testing among female sex workers. Community- or workplace-based HIV testing with outreach support from health services, peer-led HIV testing within existing social and work-based networks, and working with bosses to implement HIV prevention strategies can address low HIV testing rates in this key population.