Nanoelectromechanical (NEM) relays are excellent candidates for Field-Programmable-Gate Array (FPGA) routing due to their zero leakage and low on-resistance. Moreover, they can be fabricated using a low-temperature process and, hence, can be monolithically integrated on top of CMOS circuits. Finally, hysteresis characteristics of NEM relays can be utilized for programmable routing switches without requiring corresponding configuration SRAMs. Our simulation results demonstrate that such an approach can provide 43.6% footprint area reduction, 37% leakage power reduction, and up to 28% critical path delay reduction compared to conventional SRAM-based CMOS FPGAs at the 22nm technology node.