Diverse areas such as the Internet of Things (IoT), aerospace and industrial electronics increasingly require non-volatile memory to work under high-temperature, radiation-hard conditions, with zero standby power. Nanoelectromechanical (NEM) relays uniquely have the potential to work at 300°C and absorb high levels of radiation, with zero leakage current across the entire operational range. While NEM relays that utilise stiction for non-volatile operation have been demonstrated, it is not clear how to design a relay to reliably achieve given programming and reprogramming voltages, an essential requirement in producing a memory. Here, we develop an analytical, first-principle physics-based model of rotational NEM relays to provide detailed understanding of how the programming and reprogramming voltages vary based on the device dimensions and surface adhesion force. We then carry out an experimental parametric study of relays with a critical dimension of ≈80 nm to characterise the surface adhesion force, and derive guidelines for how a NEM relay should be dimensioned for a given contact surface force, feature size constraints and operating requirements. We carry out a scaling study to show that voltages of ≈1 V and a footprint under ≈2 μm² can be achieved with a critical dimension of ≈10 nm, with this device architecture. [2021-0138] IEEE