Tensile tests on ultrafine-grained (UFG) Cu prepared by equal channel angular pressing (ECAP) and cryo-rolling at liquid nitrogen temperature were performed at various strain rates in order to investigate size effect on their tensile plastic deformation behaviors. It was found that the tensile strength decreases with reducing specimen thickness, which is called as the first-order size effect due to the increased surface softening. A surface layer model is developed to evaluate the relationship between the degree of surface softening and the number of grains across thickness direction. Compared to coarse-grained Cu subjected to rolling at room temperature, both tensile strength and ductility of the UFG Cu after cryo-rolling are enhanced, which is ascribed to the grain refinement and the increased fraction of high angle grain boundaries. The elevated strain rate sensitivity and decreased activation volume of UFG Cu suggest that its plastic deformation mechanism is dominated by dislocation–boundary interactions.