Many studies demonstrate that partner choice has played an important role in the evolution of human cooperation, but little work has tested its impact on the evolution of human fairness. In experiments involving divisions of money, people become either over-generous or over-selfish when they are in competition to be chosen as cooperative partners. Hence, it is difficult to see how partner choice could result in the evolution of fair, equal divisions. Here, we show that this puzzle can be solved if we consider the outside options on which partner choice operates. We conduct a behavioral experiment, run agent-based simulations, and analyze a game-theoretic model to understand how outside options affect partner choice and fairness. All support the conclusion that partner choice leads to fairness only when individuals have equal outside options. We discuss how this condition has been met in our evolutionary history, and the implications of these findings for our understanding of other aspects of fairness less specific than preferences for equal divisions of resources.