Cellulose nanocrystals (CNC) obtained from biomass are increasingly demanding as a candidate for rubber composite reinforcement due to their sustainability and environmentally friendly characteristics. This work explored CNC extracted from oil palm trunks, an agricultural waste, for its reinforcing efficacy for natural rubber (NR) composite. To achieve good compatibility of the hydrophilic CNC in non-polar NR, the NR was modified in a simple and green epoxidation condition via its latex stage. The epoxidized natural rubbers (ENR) containing 15% and 25% epoxide content, symbolized as 15E and 25E, respectively, were prepared. The ENR/CNC nanocomposites were fabricated by mixing CNC aqueous suspension and ENR latex, followed by co-coagulation by methanol. A low amount of CNC (0.5–5 phr) was incorporated into the rubber and it was found that the ENR/CNC nanocomposites showed improvement in mechanical properties compared to the NR/CNC nanocomposite. The 25E/CNC nanocomposite with 1 phr of CNC achieved a 22.6% increase in tensile strength while the 25E/CNC nanocomposite with 2 phr of CNC resulted in a 27.1% increase in tear strength. The enhanced performance of the fully bio-based rubber nanocomposites is attributed to the CNC–rubber interaction and good CNC dispersion in the ENR matrices, evidenced by the results of SEM and crosslink density.