Olfactory receptors (ORs) play a key role in the prime sensorial perception, being highly relevant for intra/interspecific interactions. ORs are a subgroup of G-protein coupled receptors that exhibit highly complex subgenomes in vertebrates. However, OR repertoires remain poorly studied in fish lineages, precluding finely retracing their origin, evolution, and diversification, especially in the most basal groups. Here, we conducted an exhaustive gene screening upon 43 high-quality fish genomes exhibiting varied gene repertoires (2–583 genes). While the early vertebrates performed gas exchange through gills, we hypothesize that the emergence of new breathing structures (swim bladder and paired lungs) in early osteichthyans may be associated with expansions in the ORs gene families sensitive to airborne molecules. Additionally, we verified that the OR repertoire of moderns actinopterygians has not increased as expected following a whole genome duplication, likely due to regulatory mechanisms compensating the gene load excess. Finally, we identified 25 distinct OR families, allowing us to propose an updated universal nomenclature for the fish ORs.