Studies of the two major olfactory organs of rodents, the olfactory mucosa (OM) and the vomeronasal organ (VNO), unraveled the molecular basis of smell in vertebrates. However, some vertebrates lack a VNO. Here we generated and analyzed the olfactory transcriptome of the zebrafish and compared it to the olfactory transcriptomes of mouse to investigate the evolutionary and molecular relationship between single and dual olfactory systems. Our analyses revealed a high degree of molecular conservation, with orthologs of mouse olfactory cell-specific markers and all but one of their chemosensory receptor classes expressed in the single zebrafish olfactory organ. Zebrafish chemosensory receptor genes are expressed across a large dynamic range and their RNA abundance correlates positively with the number of neurons expressing that RNA. Thus we estimate the relative proportions of neuronal sub-types expressing different chemosensory receptors. Receptor repertoire size drives the absolute abundance of different classes of neurons, but we find similar underlying patterns in both species. Finally, we identified novel marker genes that characterize rare neuronal populations in both mouse and zebrafish. In sum, we find that the molecular and cellular mechanisms underpinning olfaction in teleosts and mammals are similar despite 430 million years of evolutionary divergence.