Thin film technology shows great promise in fabricating electronic devices such as gas sensors. Here, we report the fabrication of surface acoustic wave (SAW) sensors based on thin films of (1 − x) Ba(Ti0.8Zr0.2)O3−x(Ba0.7Ca0.3)TiO3 (BCTZ50, x = 50) and Polyethylenimine (PEI). The layers were deposited by two laser-based techniques, namely pulsed laser deposition (PLD) for the lead-free material and matrix assisted pulsed laser evaporation (MAPLE) for the sensitive polymer. In order to assay the impact of the thickness, the number of laser pulses was varied, leading to thicknesses between 50 and 350 nm. The influence of BCTZ film’s crystallographic features on the characteristics and performance of the SAW device was studied by employing substrates with different crystal structures, more precisely cubic Strontium Titanate (SrTiO3) and orthorhombic Gadolinium Scandium Oxide (GdScO3). The SAW sensors were further integrated into a testing system to evaluate the response of the BCTZ thin films with PEI, and then subjected to tests for N2, CO2 and O2 gases. The influence of the MAPLE’s deposited PEI layer on the overall performance was demonstrated. For the SAW sensors based on BCTZ/GdScO3 thin films with a PEI polymer, a maximum frequency shift of 39.5 kHz has been obtained for CO2; eight times higher compared to the sensor without the polymeric layer.