In recent years, cellulose fibers have attracted considerable attention as biofillers for natural rubber (NR) composites. However, neat cellulose cannot be used as a substitute for conventional fillers due to its poor compatibility with NR. Therefore, a new surface treatment via maleic anhydride grafted to polyisoprene (MAPI) in solution was developed to improve the filler–matrix interaction. Different contents of carbon black (CB) and cellulose fibers (before and after modification) were used as a hybrid filler system to investigate the possibility of CB substitution in NR composites. First, contact angle, Fourier transformed infrared spectrometry (FTIR), and scanning electron microscopy (SEM) techniques were used to confirm the successful cellulose surface treatment. Second, morphological analysis, Payne effect, and swelling behavior of the rubber compounds in toluene confirmed the effect of cellulose treatment on improving the interfacial filler–matrix adhesion. Finally, the results showed that the composite filled with 20 phr modified cellulose and 20 phr CB (50% replacement of CB) exhibited even better results than the composite filled with 40 phr of CB, since the tensile strength was only 7% lower, but the elongation at break, tensile modulus at 100%, and storage modulus at 25 °C were respectively 35%, 24%, and 22% higher.