Bacterial motility shows a strong evolvable feature depending on the environment. Hyper-motile E. coli could be isolated by evolving non-motile E. coli due to the mutations that enhanced transcriptional expression of the master regulator of the flagellum biosynthesis, FlhDC. These hyper-motile isolates showed reduced growth fitness but with the molecular mechanisms unrevealed. Here we obtained a novel type of hyper-motile isolates by evolving a weakly-motile E. coli K12 strain on the soft agar plates. These isolates carried high accumulated FlhDC proteins and they shared one single point mutation of ClpXV78F. The V78F affected the ATP binding to ClpX via steric repulsive effect and the mutated ClpXP protease lost most of its ability to degraded FlhDC and some other of its known targets. The signal tag of FlhDC for ClpXP recognition was also characterized. Intriguingly, in the hyper-motile strains, the highly enhanced expression of the motility genes was accompanied by the reduced expression of stress resistance genes relating to the reduced fitness of these isolates. Hence, ClpX appeared to be a novel and hot locus during the evolution of bacterial motility and the molecular mechanism of the trade-off between motility and growth was proposed for the first time.