The thermoelectric properties of spark plasma sintered, ball-milled, p-type Si80Ge20-(NaBH4)x (x = 0.7,1.7 and 2.7), and Si80Ge20B1.7-y-(NaBH4)y (y = 0.2 and 0.7) samples have been investigated from 30 K to 1100 K. These samples were prepared by spark plasma sintering of an admixture of Si, Ge, B and NaBH4 powders. In particular, the degasing process during the spark plasma sintering process, the combined results of X-ray powder diffraction, Raman spectroscopy, Hall coefficient, electrical resistivity, and Seebeck coefficient measurements indicated that NaBH4 decomposed into Na, B, Na2B29, and H2 during the spark plasma sintering process; Na and B were doped into the SiGe lattice, resulting in favorable changes in the carrier concentration and the power factor. In addition, the ball milling process and the formation of Na2B29 nanoparticles resulted in stronger grain boundary scattering of heat-carrying phonons, leading to a reduced lattice thermal conductivity. As a result, a significant improvement in the figure of merit ZT (60%) was attained in p-type Si80Ge20-(NaBH4)1.7 and Si80Ge20-B1.5(NaBH4)0.7 at 1100 K as compared to the p-type B-doped Si80Ge20 material used in the NASA’s radioactive thermoelectric generators. This single-step “doping-nanostructuring” procedure can possibly be applied to other thermoelectric materials.