Human mast cell tryptases vary strikingly in secretion, catalytic competence, and inheritance. To explore the basis of variation, we compared genes from a range of primates, including humans, great apes (chimpanzee, gorilla, orangutan), Old- and New-World monkeys (macaque and marmoset), and a prosimian (galago), tracking key changes. Our analysis reveals that extant soluble tryptase-like proteins, including alpha- and beta-like tryptases, mastins, and implantation serine proteases, likely evolved from membrane-anchored ancestors because their more deeply rooted relatives (gamma tryptases, pancreasins, prostasins) are type I transmembrane peptidases. Function-altering mutations appeared at widely separated times during primate speciation, with tryptases evolving by duplication, gene conversion, and point mutation. The alpha-tryptase Gly(216)Asp catalytic domain mutation, which diminishes activity, is present in macaque tryptases, and thus arose before great apes and Old World monkeys shared an ancestor, and before the alphabeta split. However, the Arg(-3)Gln processing mutation appeared recently, affecting only human alpha. By comparison, the transmembrane gamma-tryptase gene, which anchors the telomeric end of the multigene tryptase locus, changed little during primate evolution. Related transmembrane peptidase genes were found in reptiles, amphibians, and fish. We identified soluble tryptase-like genes in the full spectrum of mammals, including marsupial (opossum) and monotreme (platypus), but not in nonmammalian vertebrates. Overall, our analysis suggests that soluble tryptases evolved rapidly from membrane-anchored, two-chain peptidases in ancestral vertebrates into soluble, single-chain, self-compartmentalizing, inhibitor-resistant oligomers expressed primarily by mast cells, and that much of present numerical, behavioral, and genetic diversity of alpha- and beta-like tryptases was acquired during primate evolution.