We derive the structural principles of polyhedral allotropes of phosphorus, introducing three distinct families of black phosphorus nanostructures. The predicted tetrahedral, octahedral, and icosahedral phosphorus cages can also be considered as phosphorus fullerens. Phosphorus cages up to P(888) are systematically investigated by quantum chemical methods and their thermodynamic stabilities are compared with the experimentally known allotropic forms of phosphorus. The tetrahedral cages are thermodynamically favored over the octahedral and icosahedral structures, although large octahedral structures become nearly as stable as the tetrahedral ones. The stability trends of the studied polyhedral familes can be rationalized on the basis of their structural characteristics. The phosphorus polyhedra can be further stabilized by fitting smaller structures inside larger ones resulting in multilayered bulk like cages. The synthesis of the predicted black phosphorus nanostructures is suggested to be viable from the thermodynamic point of view, and several approaches for their experimental preparation can be envisaged.