The stomach, a hallmark of gnathostome evolution, represents a unique anatomical innovation characterized by the presence of acid- and pepsin-secreting glands. However, the occurrence of these glands in gnathostome species is not universal; in the nineteenth century the French zoologist Cuvier first noted that some teleosts lacked a stomach. Strikingly, Holocephali (chimaeras), dipnoids (lungfish) and monotremes (egg-laying mammals) also lack acid secretion and a gastric cellular phenotype. Here, we test the hypothesis that loss of the gastric phenotype is correlated with the loss of key gastric genes. We investigated species from all the main gnathostome lineages and show the specific contribution of gene loss to the widespread distribution of the agastric condition. We establish that the stomach loss correlates with the persistent and complete absence of the gastric function gene kit--H(+)/K(+)-ATPase (Atp4A and Atp4B) and pepsinogens (Pga, Pgc, Cym)--in the analysed species. We also find that in gastric species the pepsinogen gene complement varies significantly (e.g. two to four in teleosts and tens in some mammals) with multiple events of pseudogenization identified in various lineages. We propose that relaxation of purifying selection in pepsinogen genes and possibly proton pump genes in response to dietary changes led to the numerous independent events of stomach loss in gnathostome history. Significantly, the absence of the gastric genes predicts that reinvention of the stomach in agastric lineages would be highly improbable, in line with Dollo's principle.