Among naturally produced polymers, bacterial cellulose is receiving enormous attention due to remarkable properties, making it suitable for a wide range of industrial applications. However, the low yield, the instability of microbial strains and the limited knowledge of the mechanisms regulating the metabolism of producer strains, limit the large-scale production of bacterial cellulose. In this study, Komagataeibacter xylinus K2G30 was adapted in mannitol based medium, a carbon source that is also available in agri-food wastes. K. xylinus K2G30 was continuously cultured by replacing glucose with mannitol (2% w/v) for 210 days. After a starting lag-phase, in which no changes were observed in the utilization of mannitol and in bacterial cellulose production (cycles 1–25), a constant improvement of the phenotypic performances was observed from cycle 26 to cycle 30, accompanied by an increase in mannitol consumption. At cycle 30, the end-point of the experiment, bacterial cellulose yield increased by 38% in comparision compared to cycle 1. Furthermore, considering the mannitol metabolic pathway, D-fructose is an intermediate in the bioconversion of mannitol to glucose. Based on this consideration, K. xylinus K2G30 was tested in fructose-based medium, obtaining the same trend of bacterial cellulose production observed in mannitol medium. The adaptive laboratory evolution approach used in this study was suitable for the phenotypic improvement of K. xylinus K2G30 in bacterial cellulose production. Metabolic versatility of the strain was confirmed by the increase in bacterial cellulose production from D-fructose-based medium. Moreover, the adaptation on mannitol did not occur at the expense of glucose, confirming the versatility of K2G30 in producing bacterial cellulose from different carbon sources. Results of this study contribute to the knowledge for designing new strategies, as an alternative to the genetic engineering approach, for bacterial cellulose production.