A bacterial strain isolated from the fermentation of Colombian homemade vinegar, Gluconacetobacter medellensis, was investigated as a new source of bacterial cellulose (BC). The BC produced from substrate media consisting of various carbon sources at different pH and incubation times was quantified. Hestrin-Schramm (HS) medium modified with glucose led to the highest BC yields followed by sucrose and fructose. Interestingly, the microorganisms are highly tolerant to low pH: an optimum yield of 4.5 g/L was achieved at pH 3.5, which is generally too low for other bacterial species to function. The cellulose microfibrils produced by the new strain were characterized by scanning and transmission electron microscopy, infrared spectroscopy X-ray diffraction and elemental analysis. The morphological, structural and chemical characteristics of the cellulose produced are similar to those expected for BC.