Myxovirus resistance (Mx) proteins, which belong to the dynamin super-family, are known to inhibit RNA viral replication in a wide range of taxonomic groups, including fishes. Given their crucial role in host immune defense, the key amino acid residues in the GTP effector domain (GED) near the C-terminus are expected to evolve adaptively in order to protect the host against invading viral pathogens. The present study reveals the role of recombination and positive selection in the evolution of Mx proteins in fishes. While the GTP-binding domain in the N-terminal domain has experienced purifying selection, several amino acid residues in GED have evolved under positive selection, thus indicating adaptive evolution. Given the antiviral activity of GED, the adaptive evolutionary changes that were observed in this region are therefore predicted to be pathogen-driven.