Polyethylene terephthalate (PET) is one of the most important synthetic polymers used today. Unfortunately, the polymers accumulate in nature and to date no highly active enzymes are known that can degrade it at high velocity. Enzymes involved in PET degradation are mainly α- and β-hydrolases, like cutinases and related enzymes (EC 3.1.1). Currently, only a small number of such enzymes are well characterized. In this work, a search algorithm was developed that identified 504 possible PET hydrolase candidate genes from various databases. A further global search that comprised more than 16 Gb of sequence information within 108 marine and 25 terrestrial metagenomes obtained from the Integrated Microbial Genome (IMG) database detected 349 putative PET hydrolases. Heterologous expression of four such candidate enzymes verified the function of these enzymes and confirmed the usefulness of the developed search algorithm. In this way, two novel and thermostable enzymes with high potential for downstream application were partially characterized. Clustering of 504 novel enzyme candidates based on amino acid similarities indicated that PET hydrolases mainly occur in the phyla of Actinobacteria, Proteobacteria, and Bacteroidetes Within the Proteobacteria, the Betaproteobacteria, Deltaproteobacteria, and Gammaproteobacteria were the main hosts. Remarkably enough, in the marine environment, bacteria affiliated with the phylum Bacteroidetes appear to be the main hosts of PET hydrolase genes, rather than Actinobacteria or Proteobacteria, as observed for the terrestrial metagenomes. Our data further imply that PET hydrolases are truly rare enzymes. The highest occurrence of 1.5 hits/Mb was observed in sequences from a sample site containing crude oil.IMPORTANCE Polyethylene terephthalate (PET) accumulates in our environment without significant microbial conversion. Although a few PET hydrolases are already known, it is still unknown how frequently they appear and with which main bacterial phyla they are affiliated. In this study, deep sequence mining of protein databases and metagenomes demonstrated that PET hydrolases indeed occur at very low frequencies in the environment. Furthermore, it was possible to link them to phyla that were previously not known to harbor such enzymes. This work contributes novel knowledge on the phylogenetic relationships, the recent evolution, and the global distribution of PET hydrolases. Finally, we describe the biochemical traits of four novel PET hydrolases.