Traditional origami starts from flat surfaces, leading to crease patterns consisting of Euclidean vertices. However, Euclidean vertices are limited in their folding motions, are degenerate, and suffer from misfolding. Here we show how non-Euclidean 4-vertices overcome these limitations by lifting this degeneracy, and that when the elasticity of the hinges is taken into account, non-Euclidean 4-vertices permit higher order multistability. We harness these advantages to design an origami inverter that does not suffer from misfolding and to physically realize a tristable vertex.