Teleost fishes constitute the most species-rich vertebrate clade and exhibit extensive genetic and phenotypic variation, including diverse immune-defence 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 significant expansion of MHC I genes. Through low-coverage genome sequencing (9–39×), assembly, and comparative analyses for 66 teleost species, we here show 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 MHC I copy numbers and elevated speciation rates using trait-dependent diversification models. Our results extend the current understanding of the plasticity of the adaptive immune system and suggest an important role of immune genes in animal diversification.