Female mating preferences can influence both intraspecific sexual selection and interspecific reproductive isolation, and have therefore been proposed to play a central role in speciation. Here, we investigate experimentally in the African cichlid fish Pundamilia nyererei if differences in male coloration between three para-allopatric populations (i.e. island populations with gene flow) of P. nyererei are predicted by differences in sexual selection by female mate choice between populations. Second, we investigate if female mating preferences are based on the same components of male coloration and go in the same direction when females choose among males of their own population, their own and other conspecific populations and a closely related para-allopatric sister-species, P. igneopinnis. Mate-choice experiments revealed that females of the three populations mated species-assortatively, that populations varied in their extent of population-assortative mating and that females chose among males of their own population based on different male colours. Females of different populations exerted directional intrapopulation sexual selection on different male colours, and these differences corresponded in two of the populations to the observed differences in male coloration between the populations. Our results suggest that differences in male coloration between populations of P. nyererei can be explained by divergent sexual selection and that population-assortative mating may directly result from intrapopulation sexual selection.