Lipopolysaccharides (LPS) in the outer membrane of Gram-negative bacteria provide the first line of defense against antibiotics and other harmful compounds. LPS biosynthesis critically depends on LpxC catalyzing the first committed enzyme in this process. In Escherichia coli, the cellular concentration of LpxC is adjusted in a growth rate-dependent manner by the FtsH protease making sure that LPS biosynthesis is coordinated with the cellular demand. As a result, LpxC is stable in fast-growing cells and prone to degradation in slow-growing cells. One of the factors involved in this process is the alarmone guanosine tetraphosphate (ppGpp) but previous studies suggested the involvement of yet unknown factors in LpxC degradation. We established a quantitative proteomics approach aiming at the identification of proteins that are associated with LpxC and/or FtsH at high or low growth rates. The identification of known LpxC and FtsH interactors validated our approach. A number of proteins involved in fatty acid biosynthesis and degradation, including the central regulator FadR, were found in the LpxC and/or FtsH interactomes. Another protein associated with LpxC and FtsH was WaaH, a LPS-modifying enzyme. When overproduced, several members of the LpxC/FtsH interactomes were able to modulate LpxC proteolysis. Our results go beyond the previously established link between LPS and phospholipid biosynthesis and uncover a far-reaching network that controls LPS production by involving multiple enzymes in fatty acid metabolism, phospholipid biosynthesis and LPS modification.