Great genetic variability among teleost immunomes, with gene losses and expansions of central adaptive and innate components, has been discovered through genome sequencing over the last few years. Here, we demonstrate that the innate Myxovirus resistance gene (Mx) is lost from the ancestor of Gadiformes and the closely related Stylephorus chordatus, thus predating the loss of Major Histocompatibility Complex class II (MHCII) in Gadiformes. Although the functional implication of Mx loss is still unknown, we demonstrate that this loss is one of several ancient events appearing in successive order throughout the evolution of teleost immunity. In particular, we find that the loss of Toll-like receptor 5 predates the loss of Mx involving the entire Paracanthopterygii lineage. Using a time-calibrated phylogeny, we show that loss of MHCII and Mx overlap with major paleoclimatic and geological events indicating that these genetic changes were adaptive responses to the changing environment at the time.