The present work aims at exploiting a polyelectrolyte nanocomposite based on poly(4-styrene sulfonic acid) (PSSA) and bacterial cellulose (BC) as an eco-friendly proton-exchange membrane (PEM) for application in microbial fuel cells (MFCs). The PSSA/BC-based PEM was confirmed as a true nanocomposite by inelastic neutron scattering (INS) vibrational spectroscopy. Moreover, this PEM exhibited thermal stability up to 155 °C, Young’s modulus of 11.7 ± 0.9 GPa, ion exchange capacity of 1.85 mmol g−1, and maximum protonic conductivity of 1.73 S m−1. The application of the PSSA/BC nanocomposite membrane in a single-chamber lab-scale MFC with a pure culture of Shewanella frigidimarina yielded a maximum power density of 2.42 mW m−2, open circuit voltage of 0.436 V, and internal resistance of 15.1 kΩ. These results are superior to those obtained with a commercial Nafion® membrane and, thus, confirm the potential of this bio-based PSSA/BC nanocomposite as a PEM for MFCs.