The existence of two new allotropic forms of phosphorus, icosahedral cages and ring-shaped chains, is predicted. The cages and rings are nanostructural modifications of the black and the red phosphorus, respectively. The icosahedral and ring-shaped allotropes are compared with the experimentally known allotropic forms of phosphorus by quantum chemical methods. Both the cages and the rings are thermodynamically favored over the white phosphorus, the rings being comparable to the Hittorf's violet phosphorus and to the recently discovered fibrous red phosphorus. The stabilities of the icosahedral cages increase as a function of their size, having structural resemblance with the rhombohedral black phosphorus. The high thermodynamic stability of the phosphorus nanostructures suggests their experimental synthesis to be viable.