A two-dimensional carbon allotrope, Stone-Wales graphene, is identified in stochastic group and graph constrained searches and systematically investigated by first-principles calculations. Stone-Wales graphene consists of well-arranged Stone-Wales defects, and it can be constructed through a 90$^circ$ bond-rotation in a $sqrt{8}$$times$$sqrt{8}$ super-cell of graphene. Its calculated energy relative to graphene, +149 meV/atom, makes it more stable than the most competitive previously suggested graphene allotropes. We find that Stone-Wales graphene based on a $sqrt{8}$ super-cell is more stable than those based on $sqrt{9} times sqrt{9}$, $sqrt{12} times sqrt{12}$ and $sqrt{13} times sqrt{13}$ super-cells, and is a magic size that can be further understood through a simple energy splitting and inversion model. The calculated vibrational properties and molecular dynamics of SW-graphene confirm that it is dynamically stable. The electronic structure shows SW-graphene is a semimetal with distorted, strongly anisotropic Dirac cones.