Cetaceans, early in their evolutionary history, had developed many physiological adaptations to secondarily return to the sea. Among these adaptations, changes in molecules that transport oxygen and that ultimately support large periods of acute tissue hypoxia probably represent one big step toward the conquest of aquatic environments. Myoglobin contributes to intracellular oxygen storage and transcellular diffusion of oxygen in muscle, and plays an important role in supplying oxygen in hypoxic or ischemic conditions. Here we looked for evidence of adaptive molecular evolution of myoglobin in the cetacean lineage, relative to their terrestrial counterparts. We performed a comparative analysis to examine the variation of the parameter ω (d N/d S) and infer past period of adaptive evolution during the cetacean transition from the terrestrial to the aquatic environment. We also analyzed the changes in amino acid properties. At the nucleotide level, the results showed significant differences in selective pressure between cetacean and non-cetacean myoglobin (ω value three times higher in cetaceans when compared to terrestrial mammals), and also among cetacean lineages according to their diving capacities. Interestingly, both families with long duration diving cetaceans present two parallel substitutions (on sites 4 and 12). Regarding the amino acid properties, our analysis identified four significant physicochemical amino acid changes among residues in myoglobin protein under positive destabilizing selection.