The ATP-dependent cytoplasmic protease Lon has critical functions in protein quality control and cellular regulation in organisms across the three domains of life. In the opportunistic pathogen Pseudomonas aeruginosa, lon loss-of-function mutants exhibit multiple phenotypic defects in motility, virulence, antibiotic tolerance and biofilm formation. However, only a couple of native substrate proteins of Lon are described in P. aeruginosa until now and most of the phenotypes associated with Lon remain unexplained. Here, we searched for novel Lon substrates in P. aeruginosa by analyzing proteome-wide changes in protein levels and stabilities following lon overexpression. Our search yielded a large number of putative Lon substrates with diverse cellular functions, including metabolic enzymes, stress proteins and a significant fraction of motility-related proteins. In vitro degradation assays confirmed the metabolic protein SpeH, the heat shock protein IbpA as well as seven proteins involved in flagella- and type IV pilus-mediated motility as novel substrates of Lon. The new motility-associated substrates include both key regulators of motility (FliA, RpoN, AmrZ) as well as structural flagellar components (FliG, FliS and FlgE). Further, by isolating suppressor mutations bypassing the motility defect of lon- cells, we reveal that Lon-dependent degradation of the specific substrate SulA, a cell division inhibitor, is crucial for ensuring proper cell division and motility under optimal conditions. In sum, our work highlights Lon’s regulatory role in degrading functional proteins involved in critical cellular processes and contributes to a better molecular understanding of the pathways underlying Pseudomonas pathogenicity.