Body height influences human mate preferences and choice. A typical finding in Western societies is that women prefer men who are taller than themselves and, equivalently, men prefer women who are shorter than themselves. However, recent reports in non-Western societies (e.g., the Himba in Namibia) challenge the view on the universality of such preferences. Here we report on male and female height preferences in two non-Western populations—the Hadza (Tanzania) and the Tsimane' (Bolivia)—and the relationships between body height preferences and the height of actual partners. In the Hadza, most individuals preferred a sexual dimorphism in stature (SDS) with the man being much taller than the woman. Preferences for SDS and actual partner SDS were positively and significantly correlated in both men and women, suggesting that people who preferred larger height differences also had larger height differences with their partners. In the Tsimane', the majority of men preferred an SDS with the man being taller than the woman, but women did not show such a preference. Unlike in the Hadza, SDS preference was not significantly correlated to actual partner SDS. We conclude that patterns of height preferences and choices in the Hadza and Tsimane' are different than those observed in Western societies, and discuss possible causes for the observed differences between non-Western and Western societies.