Styrene-butadiene rubber (SBR) is widely used in the tire, footwear, and belt industries. SBR products contain a high content of carbon black, which is hazardous to human health and the environment. The goal of this study is to investigate the potential of using bio-based cellulose nanofibrils (CNFs) as a replacement for carbon black under simulated industrial formula/processing conditions. CNFs were surface-modified using five different reagents to have either -SH or -C=C functional groups grafted onto their surfaces. Vulcanized SBR sheets reinforced with pristine CNFs, and the five functionalized CNFs were prepared and their properties were tested and compared with those of industrial SBR containing carbon black. All the CNFs, pristine or modified, demonstrated higher reinforcing efficiencies (property increase/amount of reinforcement) than carbon black. The modified CNFs showed even higher reinforcing efficiencies than the pristine ones because of the former's better dispersion and stronger interfacial bonding. The -SH and -C=C functional groups reduced the hydrophilicity of CNFs and allowed chemical linkages between CNFs and SBR to be established during vulcanization. Solvent (toluene) resistance of the rubber was also improved after the incorporation of CNFs because of the barrier effect of the nanofibers and the restrained SBR chain mobility. The latter also led to reduced rubber damping. Although CNFs provide much stronger reinforcement than carbon black, going forward, SBR/CNFs/carbon black hybrid nanocomposites can also be developed to offer tailorable property combinations that meet different application requirements.