Background. Research on the evolution of reproductive isolation in African cichlid fishes has largely focussed on the role of male colours and female mate choice. Here, we tested predictions from the hypothesis that allopatric divergence in male colour is associated with corresponding divergence in preference. Methods. We studied four populations of the Lake Malawi Pseudotropheus zebra complex. We predicted that more distantly-related populations that independently evolved similar colours would interbreed freely while more closely-related populations with different colours mate assortatively. We used microsatellite genotypes or mesh false-floors to assign paternity. Fisher's exact tests as well as Binomial and Wilcoxon tests were used to detect if mating departed from random expectations. Results. Surprisingly, laboratory mate choice experiments revealed significant assortative mating not only between population pairs with differently coloured males, but between population pairs with similarly-coloured males too. This suggested that assortative mating could be based on non-visual cues, so we further examined the sensory basis of assortative mating between two populations with different male colour. Conducting trials under monochromatic (orange) light, intended to mask the distinctive male dorsal fin hues (blue v orange) of these populations, did not significantly affect the assortative mating by female P. emmiltos observed under control conditions. By contrast, assortative mating broke down when direct contact between female and male was prevented. Conclusion. We suggest that non-visual cues, such as olfactory signals, may play an important role in mate choice and behavioural isolation in these and perhaps other African cichlid fish. Future speciation models aimed at explaining African cichlid radiations may therefore consider incorporating such mating cues in mate choice scenarios.