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 H(2), therefore generating a stress build-up that causes the frequency of the device to drop. The devices are able to detect H(2) 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 H(2) safety sensors. In addition, we investigate the strongly detrimental effect that relative humidity (RH) has on the Pd responsivity to H(2), 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 muW 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.