A flexible and monolithic nanocomposite aerogel of graphitized carbon nanofibers and crystalline titania with interconnected hierarchical porosity has been fabricated through bacterial cellulose-mediated assembly and controlled pyrolysis. The fabrication is achieved in two steps: (1) formation of amorphous titania–bacterial cellulose aerogels through hydrolysis and polycondensation in a water–ethanol medium followed by lyophilisation; (2) pyrolytic treatment at 900 °C in an argon atmosphere. The nanocomposite aerogel of carbon nanofibers and crystalline titania is flexible and monolithic, and exhibits good lithium ion storage capacity and cyclability, offering a facile and low-cost approach for the fabrication of anode materials for lithium ion batteries.