Nanocrystalline Co consisting of fcc and hcp phases was processed by electrodeposition, and its mechanical properties were investigated by hardness tests. In addition, high-resolution transmission electron microscopy observations and molecular dynamics (MD) simulations were performed to investigate the grain boundary structure and dislocation nucleation from the grain boundaries. A large amount of disorders existed at the grain boundaries and stacking faults were formed from the grain boundaries in the as-deposited Co specimen. The as-deposited specimen showed a lower hardness than did the annealed specimen, although the grain size of the former was smaller than that of the latter. The activation volume of the as-deposited specimen (=1.5b(3)) was lower than that of the annealed specimen (=50b(3)), thus indicating that nucleation of dislocations from grain boundaries is more active in the as-deposited specimen than in the annealed specimens. The MD simulations showed that dislocation nucleation was closely related to a change in the defect structures at the boundary. Therefore, it is suggested that a significant amount of defects enhance changes in the defect structures at the boundary, resulting in softening of the as-deposited specimen.