Origami has recently received significant interest from the scientific community as a method for designing building blocks to construct metamaterials. However, the primary focus has been placed on their kinematic applications by leveraging the compactness and auxeticity of planar origami platforms. Here, we present volumetric origami cells—specifically triangulated cylindrical origami (TCO)—with tunable stability and stiffness, and demonstrate their feasibility as non-volatile mechanical memory storage devices. We show that a pair of TCO cells can develop a double-well potential to store bit information. What makes this origami-based approach more appealing is the realization of two-bit mechanical memory, in which two pairs of TCO cells are interconnected and one pair acts as a control for the other pair. By assembling TCO-based truss structures, we experimentally verify the tunable nature of the TCO units and demonstrate the operation of purely mechanical one- and two-bit memory storage prototypes.