Pyrroloquinoline quinone is a prominent redox cofactor in many prokaryotes, produced from a ribosomally synthesized and post-translationally modified peptide PqqA via a pathway comprising four conserved proteins PqqB-E. These four proteins are now fairly well-characterized and span radical SAM activity (PqqE), aided by a peptide chaperone (PqqD), a dual hydroxylase (PqqB), and an eight-electron, eight-proton oxidase (PqqC). A full description of this pathway has been hampered by a lack of information regarding a protease/peptidase required for the excision of an early, cross-linked di-amino acid precursor to pyrroloquinoline quinone. Herein, we isolated and characterized a two-component heterodimer protein from the α-proteobacterium Methylobacterium (Methylorubrum) extorquens that can rapidly catalyze cleavage of PqqA into smaller peptides. Using pulldown assays, surface plasmon resonance, and isothermal calorimetry, we demonstrated the formation of a complex PqqF/PqqG, with a KD of 300 nm We created a molecular model of the heterodimer by comparison with the Sphingomonas sp. A1 M16B Sph2681/Sph2682 protease. Analysis of time-dependent patterns for the appearance of proteolysis products indicates high specificity of PqqF/PqqG for serine side chains. We hypothesize that PqqF/PqqG initially cleaves between the PqqE/PqqD-generated cross-linked form of PqqA, with nonspecific cellular proteases completing the release of a suitable substrate for the downstream enzyme PqqB. The finding of a protease that specifically targets serine side chains is rare, and we propose that this activity may be useful in proteomic analyses of the large family of proteins that have undergone post-translational phosphorylation at serine.