Preferences for waist-to-hip ratio (WHR), sexual dimorphism in stature (SDS), and leg-to-body ratio (LBR) have been investigated predominantly in Western cultures. The aim of the present study was to examine the preferences of a relatively isolated, indigenous population (i.e., Yali of Papua, inhabiting the mountainous terrain east of the Baliem valley). A total of 53 women and 52 men participated in the study. Study sites differed in distance from Wamena, the biggest settlement in the region, and frequency of tourists' visits. We found that the mate preferences among Yali men and women for WHR, LBR, and SDS were not exactly the same as in Western samples. Yali preferred low women's WHR and relatively high women's (but not men's) LBR. Women's and men's ratings of each SDS set were similar, which suggests that the "male-taller norm" in Yali tribe was far weaker than in Western cultures. Additionally, the observed preferences were modified by contact with different cultures, age, and accessibility of food resources (pig possession). Our results suggest that human norms of attractiveness are malleable and can change with exposure to different environments and conditions.