Nanocrystalline (nc) materials are known to deform via mechanisms not accessible to their coarse-grained counterparts. For example, deformation twins and partial dislocations emitted from grain boundaries have been observed in nc Al and Cu synthesized by severe plastic deformation (SPD). This paper further develops an earlier dislocation-based model on the nucleation of deformation twins in nc face-centered-cubic (fcc) metals. It is found that there exists an optimum grain-size range in which deformation twins nucleate most readily. The critical twinning stress is found determined primarily by the stacking fault energy while the optimum grain size is largely determined by ratio of shear modulus to stacking fault energy. This model formulated herein is applicable to fcc nanomaterials synthesized by SPD techniques and provide a lower bound to the critical twining stress.