Origami, the ancient art of paper folding, has shown its potential as a versatile platform to design various reconfigurable structures. The designs of most origami-inspired architected materials rely on a periodic arrangement of identical unit cells repeated throughout the whole system. It is challenging to alter the arrangement once the design is fixed, which may limit the reconfigurable nature of origami-based structures. Inspired by phase transformations in natural materials, here we study origami tessellations that can transform between homogeneous configurations and highly heterogeneous configurations composed of different phases of origami unit cells. We find that extremely localized and reprogrammable heterogeneity can be achieved in our origami tessellation, which enables the control of mechanical stiffness and in-situ tunable locking behavior. To analyze this high reconfigurability and variable stiffness systematically, we employ Shannon information entropy. Our design and analysis strategy can pave the way for designing new types of transformable mechanical devices.