The genetic dissection of naturally occurring phenotypes sheds light on many fundamental and longstanding questions in speciation and adaptation and is a central research topic in evolutionary biology. Until recently, forward-genetic approaches were virtually impossible to apply to non-model organisms, but the development of next-generation sequencing techniques eases this difficulty. Here, we use the ddRAD-seq method to map a color trait with a known adaptive function in cichlid fishes, well-known textbook examples for rapid rates of speciation and astonishing phenotypic diversification. A suite of phenotypic key-innovations are related to speciation and adaptation in cichlids, among which body coloration features prominently. The focal trait of the present study, horizontal stripes, evolved in parallel in several cichlid radiations and is associated with piscivorous foraging behavior. We conducted interspecific crosses between Haplochromis sauvagei and H. nyererei, and constructed a linkage map with 867 SNP markers distributed on 22 linkage groups and total size of 1130.63cM. Lateral stripes are inherited as a Mendelian trait and map to a single genomic interval that harbors a paralog of a gene with known function in stripe patterning. Dorsolateral and midlateral stripes were always co-inherited and are thus under the same genetic control. Additionally, we directly quantify the genotyping error rates in RAD markers and offer guidelines for identifying and dealing with errors. Uncritical marker selection was found to severely impact linkage map construction. Fortunately, by applying appropriate quality control steps, a genotyping accuracy of >99.9% can be reached, thus allowing for efficient linkage-mapping of evolutionarily relevant traits.