Lanthanides were recently discovered as metals required in the active site of certain methanol dehydrogenases. Since then, the characterization of the lanthanome, that is, proteins involved in sensing, uptake, and utilization of lanthanides, has become an active field of research. Initial exploration of the response to lanthanides in methylotrophs has revealed that the lanthanome is not conserved and that multiple mechanisms for lanthanide utilization must exist. Here, we investigated the lanthanome in the obligate model methylotroph Methylobacillus flagellatus. We used a proteomic approach to analyze differentially regulated proteins in the presence of lanthanum. While multiple known proteins showed induction upon growth in the presence of lanthanum (Xox proteins, TonB-dependent receptor), we also identified several novel proteins not previously associated with lanthanide utilization. Among these was Mfla_0908, a periplasmic 19 kDa protein without functional annotation. The protein comprises two characteristic PepSY domains, which is why we termed the protein lanpepsy (LanP). Based on bioinformatic analysis, we speculated that LanP could be involved in lanthanide binding. Using dye competition assays, quantification of protein-bound lanthanides by inductively coupled plasma mass spectrometry, as well as isothermal titration calorimetry, we demonstrated the presence of multiple lanthanide binding sites that showed selectivity over the chemically similar calcium ion. LanP thus represents the first member of the PepSY family that binds lanthanides. Although the physiological role of LanP is still unclear, its identification is of interest for applications toward the sustainable purification and separation of rare-earth elements.