The Salmoniform whole-genome duplication is hypothesized to have facilitated the evolution of anadromy, but little is known about the contribution of paralogs from this event to the physiological performance traits required for anadromy, such as salinity tolerance. Here, we determined when two candidate salinity-responsive paralogs of the Na+, K+ ATPase α subunit (α1a and α1b) evolved and studied their evolutionary trajectories and tissue-specific expression patterns. We found that these paralogs arose during a small scale duplication event prior to the Salmoniform, but after the teleost, whole-genome duplication. The ‘freshwater paralog’ (α1a) is primarily expressed in the gills of Salmoniformes and an unduplicated freshwater sister-species (Esox lucius), and experienced positive selection in the fresh-water ancestor of Salmoniformes and Esociformes. Contrary to our predictions, the ‘saltwater paralog’ (α1b), which is more widely expressed than α1a, did not experience positive selection during the evolution of anadromy in the Coregoninae and Salmonine. To determine if parallel mutations in Na+, K+ ATPase α1 may contribute to salinity tolerance in other fishes, we studied independently evolved salinity-responsive Na+, K+ ATPase α1 paralogs in Anabas testudineus and Oreochromis mossambicus. We found that a quarter of the mutations occurring between salmonid α1a and α1b in functionally important sites also evolved in parallel in at least one of these species. Together, these data argue that paralogs contributing to salinity tolerance evolved prior to the Salmoniform whole-genome duplication and that strong selection and/or functional constraints have led to parallel evolution in salinity-responsive Na+, K+ ATPase α1 paralogs in fishes.