Bacterial cellulose (BC) and graphene are materials that have attracted the attention of researchers due to their outstanding properties. BC is a nanostructured 3D network of pure and highly crystalline cellulose nanofibres that can act as a host matrix for the incorporation of other nano-sized materials. Graphene features high mechanical properties, thermal and electric conductivity and specific surface area. In this paper we review the most recent studies regarding the development of novel BC-graphene nanocomposites that take advantage of the exceptional properties of BC and graphene. The most important applications of these novel BC-graphene nanocomposites include the development of novel electric conductive materials and energy storage devices, the preparation of aerogels and membranes with very high specific area as sorbent materials for the removal of oil and metal ions from water and a variety of biomedical applications, such as tissue engineering and drug delivery. The main properties of these BC-graphene nanocomposites associated with these applications, such as electric conductivity, biocompatibility and specific surface area, are systematically presented together with the processing routes used to fabricate such nanocomposites.