Using sequences of the mitochondrial NADH dehydrogenase subunit 2 gene (ND2, 1047bp) and a segment of the non-coding mitochondrial control region, as well as nuclear sequences including two introns from the S7 ribosomal protein and the loci TmoM25, TmoM27, and UME002, we explore the phylogenetic relationships of Lepidiolamprologus, one of seven lamprologine cichlid genera in Lake Tanganyika, East Africa. Analyses consisted of direct optimization using POY, including a parsimony sensitivity analysis, and maximum likelihood and Bayesian inference for comparison. With respect to Lepidiolamprologus, the results based on the mitochondrial dataset were robust to parameter variation in POY. Lepidiolamprologus cunningtoni was resolved in a large clade sister to ossified group lamprologines, among which the remaining Lepidiolamprologus were nested. In addition to L. attenuatus, L. elongatus, L. kendalli, and L. profundicola, Neolamprologus meeli, N. hecqui, N. boulengeri, N. variostigma, and two undescribed species were resolved in a two-pore Lepidiolamprologus clade sister to Lamprologus callipterus and two species of Altolamprologus. Lepidiolamprologus nkambae, in marked conflict with morphological and nuclear DNA evidence, nested outside of the two-pore Lepidiolamprologus clade, suggesting that the mtDNA signal has been convoluted by introgressive hybridization.