Genetic variation in many invasive species shows little or no signs of a founder event, suggesting that high genetic diversity may facilitate establishment success. The rocky-shore, plankton-feeding cichlid fish Cynotilapia afra is endemic to Lake Malawi, but naturally absent from many suitable sites. In the 1960s, this species was introduced to the southern areas of the lake, presumably as a result of the aquarium fish trade. It has now become established on a number of rocky areas within the Lake Malawi National Park. Here, we analysed DNA sequence variation in the mitochondrial control region of six native and four introduced populations of C. afra, and three populations of the closely-related and hybridizing Pseudotropheus zebra. In contrast to previous studies of Lake Malawi rock dwelling cichlids, network analyses suggested that native populations of C. afra showed high levels of lineage sorting in mtDNA. Introduced populations showed higher sequence and haplotype diversity than their native counterparts. Our analyses suggested that the elevated gene diversity was largely attributed to the fact that the introduced C. afra populations were derived from several genetically distinct and geographically separate populations, and to a lesser extent because of introgressive hybridization with native P. zebra. The establishment and spread of C. afra may be partly because of its ability to occupy a vacant ecological niche, but it may also have been facilitated by its enhanced genetic diversity.