Pyridoxal-5′-phosphate (PLP)-dependent proteins constitute one of the largest and most important families of enzymes in living organisms. These proteins participate in numerous biochemical processes, many of which have not been characterized, and transform substrates containing an amino group through various reactions that share aldimine as a common intermediate. Herein, we report that the PLP-dependent enzymes CcbF and LmbF, which are highly related in phylogenesis, process cysteine S-conjugated intermediates in different ways and associate with individual downstream enzyme(s) toward distinct S-functionalization of the lincosamide antibiotics celesticetin and lincomycin A. CcbF catalyzes an unusual conversion that involves decarboxylation-coupled oxidative deamination of the cysteinyl group during the formation of a two-carbon alcohol linker, whereas LmbF is responsible for β-elimination, followed by S-methylation to produce a methylmercapto group. The two tailoring routes are variable and exchangeable with each other, allowing for in vitro combinatorial biosynthesis of a number of hybrid lincosamide antibiotics, including the natural product Bu-2545. These findings demonstrate the wide diversity of PLP chemistry in enzymatic catalysis and its promising applicability in creation of new molecules.