Nano-Electro-Mechanical Switches (NEMS) are among the most promising emerging devices due to their near-zero subthreshold-leakage currents. This paper reports device fabrication and modeling, as well as novel logic gate design using "laterally-actuated double-electrode NEMS" structures. The new device structure has several advantages over existing NEMS architectures such as being immune to impact bouncing and release vibrations (unlike a vertically-actuated NEMS) and offer higher flexibility to implement compact logic gates (unlike a single-electrode NEMS). A comprehensive analytical framework is developed to model different properties of these devices by solving the Euler-Bernoulli's beam equation. The proposed model is validated using measurement data for the fabricated devices. It is shown that by ignoring the non-uniformity of the electrostatic force distribution, the existing models "underestimate" the actual value of Vpull-in and Vpull-out. Furthermore, novel energy efficient NEMS-based circuit topologies are introduced to implement compact inverter, NAND, NOR and XOR gates. For instance, the proposed XOR gate can be implemented by using only two NEMS devices compared to that of a static CMOS-based XOR gate that requires at least 10 transistors. © Copyright 2010 ACM.