Transgender women have been understudied and underserved in Paraguay; data are urgently needed to understand their HIV prevention and care needs. To estimate HIV prevalence and related risk and preventive behaviors among trans women in Paraguay, we conducted a cross-sectional survey in 2017. We employed starfish sampling – a hybrid venue-based and peer-referral method combining recruitment at randomly sampled venues and randomly selected clients from program lists, followed by short-chain referrals of eligible peers. Among 304 trans women enrolled, HIV prevalence was 24.8% (95% confidence interval [CI] 18.5–31.2%), with risk increasing with age (adjusted odds ratio [AOR] 1.06 per year, 95% CI 1.03–1.10), residence in Asunción department (AOR 4.75, 95% CI 1.57–14.36), and cocaine use (AOR 2.09, 95% CI 1.11–3.95). Trans women in Paraguay need to be prioritized for interventions with high HIV prevention efficacy. Substance use interventions to address cocaine use may also yield prevention benefits for trans women in our context.