Hydrogen sensing is essential to ensure safety in near-future zero-emission fuel cell powered vehicles. Here, we present a novel hydrogen sensor based on the resonant frequency change of a nanoelectromechanical clamped-clamped beam. The beam is coated with a Pd layer, which expands in the presence of H2, therefore generating a stress build-up that causes the frequency of the device to drop. The devices are able to detect H2 concentrations below 0.5% within 1 s of the onset of the exposure using only a few hundreds of pW of power, matching the industry requirements for H2 safety sensors. In addition, we investigate the strongly detrimental effect that relative humidity (RH) has on the Pd responsivity to H2, showing that the response is almost nullified at about 70% RH. As a remedy for this intrinsic limitation, we applied a mild heating current through the beam, generating a few micro-W of power, whereby the responsivity of the sensors is fully restored and the chemo-mechanical process is accelerated, significantly decreasing response times. The sensors are fabricated using standard processes, facilitating their eventual mass-production.