Barium hexaferrite powder samples with grains in the μm-range were obtained from solid-state sintering, and crystals with sizes up to 5 mm grown from PbO, Na2CO3, and BaB2O4 fluxes, respectively. Carbonate and borate fluxes provide the largest and structurally best crystals at significantly lower growth temperatures of 1533 K compared to flux-free synthesis (1623 K). The maximum synthesis temperature can be further reduced by the application of PbO-containing fluxes (down to 1223 K upon use of 80 at % PbO), however, Pb-substituted crystals Ba1–xPbxFe12O19 with Pb contents in the range of 0.23(2) ≤ x ≤ 0.80(2) form, depending on growth temperature and flux PbO content. The degree of Pb-substitution has only a minor influence on unit cell and magnetic parameters, although the values for Curie temperature, saturation magnetization, as well as the coercivity of these samples are significantly reduced in comparison with those from samples obtained from the other fluxes. Due to the lowest level of impurities, the samples from carbonate flux show superior quality compared to materials obtained using other methods.