Although personality traits can largely affect individual fitness we know little about the evolutionary forces generating and maintaining personality variation. Here, we investigated the hypothesis that personality variation in aggression is sexually selected in the monogamous, bi-parental cichlid Pelvicachromis pulcher. In this species, breeding pairs form territories and they aggressively defend their territory and offspring against con- and heterospecific intruders. In our mate choice study, we followed up two alternative hypotheses. We either expected females to show a directional preference for a high level and high consistency of aggression (potentially indicating mate choice for male parental quality). Alternatively, we expected females to choose males for (dis-)similarity in the level/consistency of aggression (potentially indicating mate choice for compatibility). Individual level and consistency of aggression were assessed for males and females using mirror tests. After eavesdropping on aggressive behaviour of two males (differing in level and consistency of aggression) females were then allowed to choose between the two males. Males, but not females, showed personality variation in aggression. Further, females generally preferred consistent over inconsistent males independent of their level of aggression. We did not detect a general preference for the level of male aggression. However, we found an above average preference for consistent high-aggression males; whereas female preference for inconsistent high-aggression did not deviate from random choice. Our results suggest behavioural consistency of aggression in male rainbow kribs is selected for via female mate choice. Further, our study underlines the importance of considering both the level and the consistency of a behavioural trait in studies of animal behaviour.