The HIV epidemic in Australia is changing with higher risk for HIV among newly-arrived Asian-born men who have sex with men (MSM) compared to Australian-born MSM. We evaluated the preferences for HIV prevention strategies among 286 Asian-born MSM living in Australia for <5 years. A latent class analysis uncovered three classes of respondents who were defined by their preferences: "PrEP" (52%), "Consistent condoms" (31%), and "No strategy" (17%). Compared to the "No strategy" class, men in the "PrEP" class were less likely to be a student or ask their partner for their HIV status. Men in the "Consistent condoms" class were more likely to get information about HIV from online, and less likely to ask their partner for their HIV status. Overall, PrEP was the preferred HIV prevention strategy for newly arrived migrants. Removing structural barriers to access PrEP can accelerate progress toward ending HIV transmission.