Vanadium dioxide (VO2) exhibits structural phase transition that can be triggered by thermal, electrical, and mechanical stimuli, making it a highly interesting material for MEMS/NEMS based sensors and actuators thanks to responsivity and exceptional sensitivity. For the first time, we report highly sensitive 2-terminal polycrystalline thin-film (100nm) VO2 strain sensor with 534-gauge factor, based on wafer-scale optimized Pulse Laser Deposition (PLD). Improvement in polycrystalline VO2 microstructure was fundamental to achieve this sensitive strain sensor. The proposed CMOS-compatible fabrication method of such strain sensors is scalable and expected to advance the development of new integrated strain sensors exploiting phase change materials.