Two new barium-bearing minerals: gurimite, Ba3(VO4)2 (IMA2013-032) and hexacelsian, BaAl2Si2O8 (IMA2015-045) were discovered in veins of paralava cutting gehlenite-flamite hornfels located in the Gurim Anticline in the Negev Desert, Israel. Gurimite and hexacelsian occur in oval polymineralic inclusions in paralava and are associated with gehlenite, pseudowollastonite or wollastonite, rankinite, flamite, larnite, schorlomite, andradite, fluorapatite, fluorellestadite, kalsilite, cuspidine, aradite, zadovite and khesinite. Gurimite and hexacelsian form elongate crystals <10 µm thick. The minerals are colourless and transparent with a white streak and vitreous lustre, and have (0001) cleavage, respectively good in gurimite and very good in hexacelsian. Fracture is irregular. Density calculated using empirical formulas gave 5.044 g cm–3 for gurimite and 3.305 g cm–3 for hexacelsian. Mean refractive indexes, 1.945 and 1.561, respectively, were also calculated using the empirical formulas and the Gladstone-Dale relationship. The minerals are uniaxial and nonpleochroic. The following empirical crystal chemical formulae were assigned to holotype gurimite: (Ba2.794K0.092Ca0.084Na0.033Sr0.017)Σ3.020(Al0.040Si0.005)Σ2.017O8, and holotype hexacelsian: (Ba0.911K0.059Ca0.042Na0.010)Σ1.022Al1.891Si2.034O8. The Raman spectrum of hexacelsian is similar to the one of the synthetic disordered β-BaAl2Si2O8. The Raman spectrum of gurimite is identical to that of synthetic Ba3(VO4)2. The electron back-scattered diffraction (EBSD) pattern of gurimite was fitted to the structure of its synthetic analogue with the cell parameters of Rm, a = 5.784(1), c = 21.132(1) Å, V = 612.2(2) Å3, Z = 3, giving a mean angular deviation = 0.43° (good fit). The Raman spectra of hexacelsian and its EBSD pattern suggest that natural hexacelsian corresponds to disordered synthetic β-hexacelsian P63/mcm, a = 5.2920(4) Å, c = 15.557(2) Å, α = β = 90°, γ = 120°. We suggest that after relatively fast crystallization of the main constituents of the paralava, gurimite, hexacelsian and also other Ba-bearing phases crystallized from residual melt enriched in incompatible elements that filled interstices between crystals of the main constituents.