Deciphering the mechanisms of bacterial fatty acid biosynthesis is crucial for both the engineering of bacterial hosts to produce fatty acid-derived molecules and the development of new antibiotics. However, gaps in our understanding of the initiation of fatty acid biosynthesis remain. Here, we demonstrate that the industrially relevant microbe Pseudomonas putida KT2440 contains three distinct pathways to initiate fatty acid biosynthesis. The first two routes employ conventional β-ketoacyl-ACP synthase III enzymes, FabH1 and FabH2, that accept short- and medium-chain-length acyl-CoAs, respectively. The third route utilizes a malonyl-ACP decarboxylase enzyme, MadB. A combination of exhaustive in vivo alanine-scanning mutagenesis, in vitro biochemical characterization, X-ray crystallography, and computational modeling elucidate the presumptive mechanism of malonyl-ACP decarboxylation via MadB. Given that functional homologs of MadB are widespread throughout domain Bacteria, this ubiquitous alternative fatty acid initiation pathway provides new opportunities to target a range of biotechnology and biomedical applications.