A layered structure combining a thin plate of lithium niobate (LN) with a langasite (LGS) substrate was numerically investigated as an advanced substrate material for surface acoustic wave (SAW) devices with improved characteristics, including capability of operating at high temperatures. The longitudinal leaky SAWs (LLSAWs) propagating with negligible attenuation and high velocities up to 6400 m/s were found in LN/LGS using an optimization technique previously applied to the LN/quartz structure. Compared with quartz, the use of LGS as a substrate imposes less constrains on bonding at elevated temperatures for fabrication of a layered structure. Due to the specific acoustic anisotropy of LGS crystals, low-attenuated high-velocity waves exist in a wide range of LGS orientations, including the commercially available SAW cut, when LGS substrate is combined with an LN plate. In the found optimal structures, the electromechanical coupling increased from 5.5% to 14.5%, with increasing LN thickness, making LN/LGS substrate suitable for application in SAW devices with a widely varying bandwidth. In addition, low shear bulk wave velocities in LGS provide a wide spurious-free frequency range in resonators using LLSAW.