Teleost fishes constitute the most species-rich vertebrate clade and exhibit extensive genetic and phenotypic variation, including diverse immune defense strategies. The genomic basis of a particularly aberrant strategy is exemplified by Atlantic cod, in which a loss of major histocompatibility complex (MHC) II functionality coincides with a marked expansion of MHC I genes. Through low-coverage genome sequencing (9–39×), assembly and comparative analyses for 66 teleost species, we show here that MHC II is missing in the entire Gadiformes lineage and thus was lost once in their common ancestor. In contrast, we find that MHC I gene expansions have occurred multiple times, both inside and outside this clade. Moreover, we identify an association between high MHC I copy number and elevated speciation rates using trait-dependent diversification models. Our results extend current understanding of the plasticity of the adaptive immune system and suggest an important role for immune-related genes in animal diversification.