Two-dimensional (2D) structures from layered materials have enabled a number of novel devices including resonant nanoelectromechanical systems (NEMS). 2D NEMS resonators are highly responsive to strain, allowing their resonance frequencies to be efficiently tuned over broad ranges, which is a feature difficult to attain in conventional micromachined resonators. In electrically configured and tuned devices, high external voltages are typically required to set and maintain different frequencies, limiting their applications. Here we experimentally demonstrate molybdenum disulfide (MoS2) nanomechanical resonators that can be reconfigured between different frequency bands with zero maintaining voltage in a non-volatile fashion. By leveraging the thermal hysteresis in these 2D resonators, we use heating and cooling pulses to reconfigure the device frequency, with no external voltage required to maintain each frequency. We further show that the frequency spacing between the bands can be tuned by the thermal pulse strength, offering full control over the programmable operation. Such reconfigurable MoS2 resonators may provide an alternative pathway toward small-form-factor and low-power tunable devices in future reconfigurable radio-frequency circuits with multi-band capability.