Background: Women new to sex work and those with a greater degree of mobility have higher risk of HIV infection. Using social capital as a theoretical framework, we argue that better understanding of the interactions of micro-level structural factors can be valuable in reshaping and restructuring health promotion programmes in Bali to be more responsive to the concerns and needs of newcomer and mobile female sex workers (FSWs). Methods. We conducted interviews with 11 newcomer FSWs (worked < six months), 9 mobile FSWs (experienced but worked at the current brothel < six months), and 14 senior FSWs (experienced and worked at current brothel > six months). The interviews explored women's experience of sex work including how and why they came to sex work, relationships with other FSWs and their HIV prevention practices. Results: A thematic framework analysis revealed newcomer FSWs faced multiple levels of vulnerability that contributed to increased HIV risk. First, a lack of knowledge and self-efficacy about HIV prevention practices was related to their younger age and low exposure to sexual education. Second, on entering sex work, they experienced intensely competitive working environments fuelled by economic competition. This competition reduced opportunities for positive social networks and social learning about HIV prevention. Finally, the lack of social networks and social capital between FSWs undermined peer trust and solidarity, both of which are essential to promote consistent condom use. For example, newcomer FSWs did not trust that if they refused to have sex without a condom, their peers would also refuse; this increased their likelihood of accepting unprotected sex, thereby increasing HIV risk. Conclusions: Public health and social welfare interventions and programmes need to build social networks, social support and solidarity within FSW communities, and provide health education and HIV prevention resources much earlier in women's sex work careers.