It has been suggested that certain physical cues can be used to predict mate quality and that sensitivity to these cues would therefore be adaptive. From this, it follows that in environments where the optimal values for these features differ, the attractiveness preferences should also be different. In this study, we show that there are striking differences in attractiveness preferences for female bodies between United Kingdom (UK) Caucasian and South African Zulu observers. These differences can be explained by different local optima for survival and reproduction in the two environments. In the UK, a high body mass is correlated with low health and low fertility, and the converse is true in rural South Africa. We also report significant changes in the attractiveness preferences of Zulus who have moved to the UK. This suggests that these preferences are malleable and can change with exposure to different environments and conditions. Additionally, we show that Britons of African origin, who were born and who grew up in the UK, have exactly the same preferences as our UK Caucasian observers. These results suggest that humans have mechanisms for acquiring norms of attractiveness that are highly plastic, which allow them to track different ecological conditions through learning.