Emerging applications such as the Internet-of-Things and more-electric aircraft require electronics with integrated data storage that can operate in extreme temperatures with high energy efficiency. As transistor leakage current increases with temperature, nanoelectromechanical relays have emerged as a promising alternative. However, a reliable and scalable non-volatile relay that retains its state when powered off has not been demonstrated. Part of the challenge is electromechanical pull-in instability, causing the beam to snap in after traversing a section of the airgap. Here we demonstrate an electrostatically actuated nanoelectromechanical relay that eliminates electromechanical pull-in instability without restricting the dynamic range of motion. It has several advantages over conventional electrostatic relays, including low actuation voltages without extreme reduction in critical dimensions and near constant actuation airgap while the device moves, for improved electrostatic control. With this nanoelectromechanical relay we demonstrate the first high-temperature non-volatile relay operation, with over 40 non-volatile cycles at 200 ∘C.