Centimeter-sized single crystals of Ba2LaFeNb4O15 were grown from a high-temperature solution by using LiBO2 flux and a sealed platinum assembly. The obtained single crystals display the same physical properties as their ceramic counterparts. A frequency-dependent dielectric permittivity maximum was found (Tm = 100 K at 5 kHz), which indicates relaxor behavior. Magnetic susceptibility measurements revealed purely paramagnetic behavior between 10 and 350 K. X-ray diffraction measurements of Ba2LaFeNb4O15 single crystals revealed an incommensurate structure at room temperature with a bidimensional modulation characterized by vectors q1 = (, , 1/2) and q2 = (, , 1/2) with = 0.295(1). This crystal growth method offers a promising elaboration route to centimeter-sized crystals of niobate-based compounds, which may not be grown from the pure liquid phase, especially those with a tetragonal tungsten bronze (TTB) structure.