Understanding the genetic basis of novel traits is a central topic in evolutionary biology. Two novel pigmentation phenotypes, egg-spots and blotches, emerged during the rapid diversification of East African cichlid fishes. Egg-spots are circular pigmentation markings on the anal fins of hundreds of derived haplochromine cichlids species, whereas blotches are patches of conspicuous anal fin pigmentation with ill-defined boundaries that occur in few species that belong to basal cichlid lineages. Both traits play an important role in the breeding behavior of this group of fishes. Knowledge about the origin, homology and underlying genetics of these pigmentation traits is sparse.; Here, we present a comparative transcriptomic and differential gene expression analysis of egg-spots and blotches. We first conducted an RNA sequencing experiment where we compared egg-spot tissue with the remaining portion of egg-spot-free fin tissue using six individuals of Astatotilapia burtoni. We identified 1229 differentially expressed genes between the two tissue types. We then showed that rates of evolution of these genes are higher than average estimated on whole transcriptome data. Using quantitative real-time PCR, we found that 29 out of a subset of 46 differentially expressed genes showed an analogous expression pattern in another haplochromine species' egg-spots, Cynotilapia pulpican, strongly suggesting that these genes are involved in the egg-spot phenotype. Among these are the previously identified egg-spot gene fhl2a, two known patterning genes (hoxC12a and bmp3) as well as other pigmentation related genes such as asip. Finally, we analyzed the expression patterns of the same gene subset in two species that feature blotches instead of egg-spots, one haplochromine species (Pseudocrenilabrus philander) and one ectodine species (Callochromis macrops), revealing that the expression patterns in blotches and egg-spots are rather distinct.; We identified several candidate genes that will serve as an important and useful resource for future research on the emergence and diversification of cichlid fishes' egg-spots. Only a limited degree of conservation of gene expression patterns was detected between the egg-spots of the derived haplochromines and blotches from ancestral haplochromines, as well as between the two types of blotches, suggesting an independent origin of these traits.