Metalloprotein discovery is often made post hoc, in which activity studies following protein isolation reveal a metal-ion dependence. Herein we take a different approach to finding metalloproteins, by building on the discovery of copper-containing lytic polysaccharide monooxygenases (LPMOs), which—as part of their protein sequences—contain an N-terminus histidine. This residue acts as a natural chelator for transition metal ions, irrespective of the structure of the protein. We report the method of signal strapping, where sequences of N-terminal signal peptides artificially appended with a histidine residue at their C-terminus are used to bootstrap a proteomic search. These searches return sequences of proteins with an N-terminus histidine capable of coordinating a metal ion. We exemplify the approach by the discovery and characterisation of four new classes of bacterial metalloproteins, including two which we denote as anglerases due to their potential to capture various transition metal ions from the surroundings of bacteria.