The failure strengths of graphene grain boundaries, over a range of misorientation angles from 0° to 60°, are investigated by molecular dynamics simulations. A correlation between the level of bond pre-strain and bond rupture is revealed. It is shown that the distribution of grain boundary dislocations is, in addition to the misorientation angle, also an important factor in determining the failure strength. For grain boundaries featuring a uniform dislocation distribution, a higher misorientation angle will yield a higher failure strength as a result of overlapping and mutual cancelation of the strain fields of neighboring dislocations. For grain boundaries with a non-uniform dislocation distribution, however, local structural inhomogeneity introduces large local tensile stresses and the failure strength decreases significantly. Therefore, a complicated interplay exists between the dislocation density and distribution, and the failure strength of graphene grain boundaries.