Integrated circuits with memory elements are provided. An integrated circuit may include logic circuitry formed in a first portion having complementary metal-oxide-semiconductor (CMOS) devices and may include at least a portion of the memory elements and associated memory circuitry formed in a second portion having nano-electromechanical (NEM) relay devices. The NEM and CMOS devices may be interconnected through vias in a dielectric stack. Devices in the first and second portions may receive respective power supply voltages. In one suitable arrangement, the memory elements may include two relay switches that provide nonvolatile storage characteristics and soft error upset (SEU) immunity. In another suitable arrangement, the memory elements may include first and second cross-coupled inverting circuits. The first inverting circuit may include relay switches, whereas the second inverting circuit includes only CMOS transistors. Memory elements configured in this way may be used to provide volatile storage characteristics and SEU immunity.