We have investigated the structural and electronic characteristics of tetrahedral, octahedral, and icosahedral fullerenes composed of group 15 elements phosphorus, arsenic, antimony, and bismuth. Systematic quantum chemical studies at the DFT and MP2 levels of theory were performed to obtain periodic trends for the structural principles, stabilities, and electronic properties of the elemental nanostructures. Calibration calculations for polyhedral clusters with up to 20 atoms showed the applied theoretical approaches to be in good agreement with high-level CCSD(T)/cc-pVTZ results. By studying fullerenes up to P(888), As(540), Sb(620), and Bi(620), we found their structures and stabilities to converge smoothly toward their experimental bulk counterparts. The diameters of the largest studied cages were 4.8, 3.7, 4.8, and 5.1 nm for the P, As, Sb, and Bi fullerenes, respectively. Comparisons with the experimentally known allotropes of the studied elements suggest the predicted polyhedral cages to be thermodynamically stable. All studied group 15 polyhedral fullerenes were found to be semiconducting, and density of states analysis illustrated clear periodic trends in their electronic structure. Relativistic effects become increasingly important when moving from P to Bi and taking the spin-orbit effects into account by using a two-component procedure had a significant positive effect on the relative stability of bismuth clusters.