After reports of unusually low oxidation states of lanthanide elements in Ln-B clusters and their inverse sandwich geometrical topologies, the interest shifted from boride clusters doped with transition metal (TM) elements to the boride clusters doped with lanthanide atoms. In this work, the results obtained by a combined approach consisting of CALYPSO structure predictions and density functional theory (DFT) calculations for the neutral and anionic PrBn series, n = 7-16, are reported. A close agreement between our calculated vertical detachment energies and experimental data supports the accuracy of the results obtained. Contrary to the medium-size TM-doped medium boron clusters, which prefer three types of structural configurations, all lowest-energy states of the medium-size Pr-doped boron clusters have half-sandwich geometries. An interesting structural evolution pattern was found for both neutral and anionic PrBn clusters at n = 7, 10, 13, and 16, which includes quasi-planar B7 units half-sandwiching the Pr atom. Unusual oxidation numbers of +2 and +1 were found for the Pr atom in the PrB7- and PrB8- anions, respectively. Chemical bonding analysis for the neutral PrB7 and PrB13 clusters revealed that their high stability stems from interactions between Pr 5d and B 2p orbitals. A stable tubular-shaped PrB30 cluster is proposed as a promising building block for boron-based nanotubes.