We report an experimental system in which Escherichia coli evolves into an insect mutualist. When the essential gut symbiont of the stinkbug Plautia stali was replaced by E. coli, a few survivor insects exhibited specific localization and vertical transmission of E. coli. Through trans-generational maintenance with P. stali, several hyper-mutating E. coli lines independently evolved host’s high adult emergence and improved body color. Such “mutualistic” E. coli lines exhibited independent mutations disrupting the carbon catabolite repression (CCR) global transcriptional regulator. Each of the mutations reproduced the mutualistic phenotypes when introduced into wild-type E. coli, confirming that the single CCR mutations instantly make E. coli an insect mutualist. Our discovery uncovers that evolution of elaborate mutualism can proceed more easily and rapidly than conventionally envisaged.