Ultra-sensitive and responsive humidity sensors were fabricated by deposition of graphene oxide (GO) on laser-induced graphene (LIG) electrodes fabricated by a low-cost visible laser scribing tool. The effects of GO layer thickness and electrode geometry were investigated. Sensors comprising 0.33 mg/mL GO drop-deposited on spiral LIG electrodes exhibited high sensitivity up to 1800 pF/% RH at 22 °C, which is higher than previously reported LIG/GO sensors. The high performance was ascribed to the high density of the hydroxyl groups of GO, promoted by post-synthesis sonication treatment, resulting in high water physisorption rates. As a result, the sensors also displayed good stability and short response/recovery times across a wide tested range of 0–97% RH. The fabricated sensors were benchmarked against commercial humidity sensors and displayed comparable performance and stability. Finally, the sensors were integrated with a near-field communication tag to function as a wireless, battery-less humidity sensor platform for easy read-out of environmental humidity values using smartphones.