Cichlid fishes are emblematic models for the study of adaptive radiation, driven by natural and sexual selection. Parasite mediated selection is an important component in these processes, and the evolution of their immune system therefore merits special attention. In this study, light is shed on the phylogeny of the b family of cichlid major histocompatibility complex (MHC) class IIB genes. Full-length coding sequences were used to reconstruct phylogenies using criteria of maximum parsimony, maximum likelihood and Bayesian inference. All analyses suggest monophyly of the b family of cichlid MHC class IIB genes, although sequences of the cichlid sister taxa are currently not available. Two evolutionary lineages of these genes, respectively encompassing the recently defined genomic regions DBB-DEB-DFB and DCB-DDB, show highly contrasting levels of differentiation. To explore putative causes for these differences, exon 2 sequences were screened for variation in recombination rate and strength of selection. The more diversified lineage of cichlid MHC class IIB b genes was found to have higher levels of both recombination and selection. This is consistent with the observation in other taxa that recombination facilitates the horizontal spread of positively selected sites across MHC loci and hence contributes to fast sequence evolution. In contrast, the lineage that showed low diversification might either be under stabilizing selection or is evolutionary constrained by its low recombination rate. We speculate whether this lineage might include MHC genes with non-classical functions.