The leptin gene has received intensive attention and scientific investigation for its importance in energy homeostasis and reproductive regulation in mammals. Furthermore, study of the leptin gene is of crucial importance for public health, particularly for its role in obesity, as well as for other numerous physiological roles that it plays in mammals. In the present work, we report the identification of novel leptin genes in 4 species of Cetacea, and a comparison with 55 publicly available leptin sequences from mammalian genome assemblies and previous studies. Our study provides evidence for positive selection in the suborder Odontoceti (toothed whales) of the Cetacea and the family Phocidae (earless seals) of the Pinnipedia. We also detected positive selection in several leptin gene residues in these two lineages. To test whether leptin and its receptor evolved in a coordinated manner, we analyzed 24 leptin receptor gene (LPR) sequences from available mammalian genome assemblies and other published data. Unlike the case of leptin, our analyses did not find evidence of positive selection for LPR across the Cetacea and Pinnipedia lineages. In line with this, positively selected sites identified in the leptin genes of these two lineages were located outside of leptin receptor binding sites, which at least partially explains why co-evolution of leptin and its receptor was not observed in the present study. Our study provides interesting insights into current understanding of the evolution of mammalian leptin genes in response to selective pressures from life in an aquatic environment, and leads to a hypothesis that new tissue specificity or novel physiologic functions of leptin genes may have arisen in both odontocetes and phocids. Additional data from other species encompassing varying life histories and functional tests of the adaptive role of the amino acid changes identified in this study will help determine the factors that promote the adaptive evolution of the leptin genes in marine mammals.