Surface acoustic wave (SAW)-based formaldehyde gas sensor using bi-layer nanofilms of bacterial cellulose (BC) and polyethyleneimine (PEI) was developed on an ST-cut quartz substrate using sol-gel and spin coating processes. BC nanofilms significantly improve the sensitivity of PEI films to formaldehyde gas, and reduces response and recovery times. The BC films have superfine filamentary and fibrous network structures, which provide a large number of attachment sites for the PEI particles. Measurement results obtained using in situ diffuse reflectance Fourier transform infrared spectroscopy showed that the primary amino groups of PEI strongly adsorb formaldehyde molecules through nucleophilic reactions, thus resulting in a negative frequency shift of the SAW sensor due to the mass loading effect. In addition, experimental results showed that the frequency shifts of the SAW devices are determined by thickness of PEI film, concentration of formaldehyde and relative humidity. The PEI/BC sensor coated with three layers of PEI as the sensing layer showed the optimal sensing performance, which had a frequency shift of 35.6 kHz for 10 ppm formaldehyde gas, measured at room temperature and 30 % RH. The sensor also showed good selectivity and stability, with a low limit of detection down to 100 ppb.