Taste receptor genes are functionally important in animals, with a surprising exception in the bottlenose dolphin, which shows extensive losses of sweet, umami, and bitter taste receptor genes. To examine the generality of taste gene loss, we examined seven toothed whales and five baleen whales and sequenced the complete repertoire of three sweet/umami (T1Rs) and ten bitter (T2Rs) taste receptor genes. We found all amplified T1Rs and T2Rs to be pseudogenes in all 12 whales, with a shared premature stop codon in 10 of the 13 genes, which demonstrated massive losses of taste receptor genes in the common ancestor of whales. Furthermore, we analyzed three genome sequences from two toothed whales and one baleen whale and found that the sour taste marker gene Pkd2l1 is a pseudogene, whereas the candidate salty taste receptor genes are intact and putatively functional. Additionally, we examined three genes that are responsible for taste signal transduction and found the relaxation of functional constraints on taste signaling pathways along the ancestral branch leading to whales. Together, our results strongly suggest extensive losses of sweet, umami, bitter, and sour tastes in whales, and the relaxation of taste function most likely arose in the common ancestor of whales between 36 and 53 Ma. Therefore, whales represent the first animal group to lack four of five primary tastes, probably driven by the marine environment with high concentration of sodium, the feeding behavior of swallowing prey whole, and the dietary switch from plants to meat in the whale ancestor.