Multiple challenges expose American Indian and Alaska Native (AIAN) women to high-risk sexual partnerships and increased risk for HIV/STI. Using a unique sample of sexually-active young AIAN women (n = 129), we examined characteristics of last three partners and whether transitional partnerships were associated with different risk profiles, including where partners met, lived, and had sex. Respondents were more likely to have met their previous or current secondary partner (P2) at a friend’s or family setting (versus work or social setting) (AOR = 3.92; 95 % CI 1.31, 11.70). Condom use was less likely when meeting a partner at friend’s or family settings (AOR = 0.17; 95 % CI 0.05, 0.59). Sexual intercourse with P2 (compared to P1) usually took place in “riskier” settings such as a car, bar, or outside (AOR = 4.15; 95 % CI 1.59, 10.68). Perceived “safe” places, e.g., friend’s or family’s house, were identified with risky behaviors; thus, homogeneous messaging campaigns may promote a false sense of safety.