Plastic waste has accumulated rapidly in the past century and is now found throughout every ecosystem on Earth. Its ubiquitous presence means that plastic is routinely ingested by countless organisms, with potential negative consequences for organismal health. New solutions are urgently needed to combat plastic pollution. Among the many strategies required to curb the plastic pollution crisis, the bioremediation of plastic via enzymatic activity of microbial species represents a promising approach. Diverse microbes harbor enzymes capable of degrading plastic polymers and utilizing the polymers as a carbon source. Herein, we characterize the landscape of microbial protein-coding sequences with potential plastic degrading capability. Using the two enzyme systems of PETase and MHETase as a guide, we combined sequence motif analysis, phylogenetic inference, and machine learning-guided 3D protein structure prediction to pinpoint potential plastic-degrading enzymes. Our analysis platform identified hundreds of enzymes from diverse microbial taxa with similarity to known PETases, and far fewer enzymes with similarity to known MHETases. Phylogenetic reconstruction revealed that the plastic degrading enzymes formed distinct clades from the sequences of ancestral enzymes. Among the potential candidate sequences, we pinpointed both a PETase-like and MHETase-like enzyme within the bacterium Pseudomonas stutzeri. Using plate clearing assays, we demonstrated that P. stutzeri is capable of degrading both polyurethane (Impranil®) and polycaprolactone (PCL). Pseudomonas stutzeri also grew on carbon-free agar supplemented with polystyrene, suggesting this organism can utilize synthetic polymers as a carbon source. Overall, our integrated bioinformatics and experimental approach provides a rapid and low-cost solution to identify and test novel polymer-degrading enzymes for use in the development of plastic bioremediation technologies.