The wear resistance of pure rubber materials is very limited in engineering applications, such as pneumatic or sealing elements. In order to improve their wear resistance, various fillers were incorporated into the rubber matrix. In this background, the present work deals with the investigations of the mechanical and tribological properties of SBR/NR rubber composites containing 1 part per hundred rubber (phr) graphene and cellulose nanocrystal (CNC), respectively. The sliding wear tests were performed on a block-on-ring tribometer against a 100Cr6 bearing steel ring under dry sliding conditions. The results revealed that the incorporation of graphene and CNC slightly increases the storage modulus and decreases the hysteresis loss. However, the glass transition temperature was not affected. In the studied range of load conditions, it was found that the friction and wear properties of the rubber composites strongly depend on the normal load and sliding velocity. The wear resistance was obviously improved, especially under low F·v-factors, when CNC were introduced into the rubber composite. Under F·v-condition of 12 N and 0.1 ms−1, the specific wear rate was reduced by approximate 70% after addition of CNC compared to that of the benchmark material. The optical analysis of the wear track on the steel counterface reveals that this low wear rate can be attribute to the formation of a thin tribofilm on the steel disc surface.