The cichlid fishes in the East African Great Lakes are a prime model system for the study of adaptive radiation. Therefore, the availability of an elaborate phylogenetic framework is an important prerequisite. Previous phylogenetic hypotheses on East African cichlids are mainly based on mitochondrial and/or fragment-based markers, and, to date, no taxon-rich phylogeny exists that is based on multilocus DNA sequence data. Here, we present the design of an extensive new primer set (24 nuclear makers) for East African cichlids that will be used for multilocus phylogenetic analyses in the future. The primers are designed to work for both Sanger sequencing and next-generation sequencing with the 454 technology. As a proof of principle, we validate these primers in a phylogenetically representative set of 16 cichlid species from Lake Tanganyika and main river systems in the area and provide a basic evaluation of the markers with respect to marker length and diversity indices.