A series of elastomeric nanocomposites with superior tensile strength and extensibility, simultaneously exhibiting softening, was prepared using in situ polymerization by homogeneously dispersing TEMPO-oxidized cellulose individualized nanofibers (TOCNs) in a polyurethane urea (PUU) matrix. The structure of these PUU composites covalently cross-linked with the TOCNs was characterized. It was interesting to find that the amount and size of the hard domains in the composites gradually decreased by introducing crosslinkable TOCNs. With only 2wt% of TOCNs incorporated, a 10.4-fold increase in tensile strength, 5.5-fold increase in strain-to-failure, and a decrease of 35% in the coefficient of thermal expansion were achieved, compared with those of neat PUU. However, the elastic modulus of the nanocomposites gradually decreased with up to 1wt% of TOCNs. Conversely, with 2wt% of TOCNs, the stiffness of the elastomers again increased, due to filler-filler interaction over the CNFs percolation in the nanocomposites.