Emulsified asphalt is the primary material for preventive maintenance and cold-mix paving, but its low cohesive strength and poor mechanical properties limit its wide application, even with polymer modification. In this study, Styrene-Butadiene Rubber (SBR) emulsified asphalt was modified with nano-cellulose materials, namely nano paper-cellulose (NPC) and wood-derived nano-cellulose (WDC), to improve its properties. A novel preparation method of nano-cellulose solution was developed, including blending, ultrasonic stirring, and centrifugal treatment. Four types of nano-cellulose solution (0.5% NPC, 0.5%, 1.0%, and 1.5% WDC by weight of water) were selected. The microscopy analysis indicated that 0.5% WDC emulsion had a smaller particle size than 1.5% WDC emulsion. The rheology test indicated that WDC modified residue improved rutting resistance with the increased solution dosage due to the cross-linking effect, but its creep-and-recovery performance was worse than that of SBR emulsion residue. The NPC modified binder had a higher rutting factor than WDC modified binder at the same dosage after short-term aging. In addition, 1.0% WDC could be regarded as the optimal dosage in terms of fatigue and low-temperature performance. Furthermore, Fourier Transform Infrared Spectroscopy (FTIR) results showed that 0.5% NPC modified residue performed better in long-term aging resistance compared with 0.5%WDC modified asphalt.