Moral evolution theories have emphasized kinship, reciprocity, group selection, and equilibrium selection. Yet, moral virtues are also sexually attractive. Darwin suggested that sexual attractiveness may explain many aspects of human morality. This paper updates his argument by integrating recent research on mate choice, person perception, individual differences, costly signaling, and virtue ethics. Many human virtues may have evolved in both sexes through mutual mate choice to advertise good genetic quality, parenting abilities, and/or partner traits. Such virtues may include kindness, fidelity, magnanimity, and heroism, as well as quasi-moral traits like conscientiousness, agreeableness, mental health, and intelligence. This theory leads to many testable predictions about the phenotypic features, genetic bases, and social-cognitive responses to human moral virtues.