We investigate a previously unknown phase of phosphorus that shares its layered structure and high stability with the black phosphorus allotrope. We find the in-plane hexagonal structure and bulk layer stacking of this structure, which we call `blue phosphorus', to be related to graphite. Unlike graphite and black phosphorus, blue phosphorus displays a wide fundamental band gap and should exfoliate easily to form quasi-2D structures suitable for electronic applications. We study a likely transformation pathway from black to blue phosphorus and discuss possible ways to synthesize the new structure.