Lake Malawi contains a flock of >500 species of cichlid fish that have evolved from a common ancestor within the last million years. The rapid diversification of this group has been attributed to morphological adaptation and to sexual selection, but the relative timing and importance of these mechanisms is not known. A phylogeny of the group would help identify the role each mechanism has played in the evolution of the flock. Previous attempts to reconstruct the relationships among these taxa using molecular methods have been frustrated by the persistence of ancestral polymorphisms within species. Here we describe results from a DNA fingerprinting technique that overcomes this problem by examining thousands of polymorphisms distributed across the genome. The resulting dendrogram averages the evolutionary history of thousands of genes and should accurately reflect the evolutionary history of these species. Our tree resolves relationships among closely related Lake Malawi cichlids and provides insights into the pattern of speciation in this group. We demonstrate that adaptive divergence in trophic morphology played an important role during the early history of the lake. Subsequent species diversity has arisen with little change in trophic morphology, which suggests that other forces are responsible for the continued speciation of these fishes.