Lon is a major ATP-dependent protease of E. coli involved in degradation of abnormal misfolded proteins and specific regulatory proteins. Absence of Lon in E. coli results in sensitivity to DNA damaging agents and over-production of capsular polysaccharide due to accumulation of Lon substrates, SulA (cell division inhibitor induced upon DNA damage) and RcsA (activator of cps genes), respectively. In a previous study, we identified that a G232D mutation, termed faa (for function affecting alternative-lon-protease), in the E. coli co-chaperone DnaJ, results in suppression of lon mutant phenotypes. Additionally, inactivation of the trans-translation system was found to have an additive effect on faa activity. In the present work, we employed random mutagenesis approach to isolate novel mutations in dnaJ which could phenotypically compensate the absence of Lon. Using a lacZ-based Lon reporter strain, we were able to isolate two new mutations in dnaJ as lon suppressors. These mutations, namely, flm-1 (H33Y) and flm-2 (P34S), affected the highly conserved HPD motif of DnaJ. Both mutations suppressed lon phenotypes to variable extent and the suppression was also differentially modulated by mutations in ssrA that affect trans-translation. We show that ClpYQ protease up-regulated in both mutants should degrade SulA, since inactivation of clpQ abolished the resistance to DNA damaging agents. On the other hand, we found suppression of capsule overproduction phenotype was independent of ClpYQ in both mutants but resulted due to down-regulation of rcsA in flm-1. Thus, our findings highlight the intricate redundancy of cellular proteolysis networks in bacteria which can compensate the absence of Lon via distinct mechanisms.