The emergence of drug-resistant bacteria calls for the discovery of new antibiotics. Yet, for decades, traditional discovery strategies have not yielded new classes of antimicrobial. Here, by mining the human proteome via an algorithm that relies on the sequence length, net charge, average hydrophobicity and other physicochemical properties of antimicrobial peptides, we report the identification of 2,603 encrypted peptide antibiotics that are encoded in proteins with biological function unrelated to the immune system. We show that the encrypted peptides kill pathogenic bacteria by targeting their membrane, modulate gut and skin commensals, do not readily select for bacterial resistance, and possess anti-infective activity in skin abscess and thigh infection mouse models. We also show, in vitro and in the two mouse models of infection, that encrypted antibiotic peptides from the same biogeographical area display synergistic antimicrobial activity. Our algorithmic strategy allows for the rapid mining of proteomic data and opens up new routes for the discovery of candidate antibiotics.