Software-defined metamaterials (SDMs) represent a novel paradigm for real-time control of metamaterials. SDMs are envisioned to enable a variety of exciting applications in the domains such as smart textiles and sensing in challenging conditions. Many of these applications envisage deformations of the SDM structure (e.g., rolling, bending, stretching). This affects the relative position of the metamaterial elements and requires their localization relative to each other. The question of how to perform such localization is, however, yet to spark in the community. We consider that the metamaterial elements are controlled wirelessly through a Terahertz (THz)-operating nanonetwork. Moreover, we consider the elements to be energy constrained, with their sole powering option being to harvest environmental energy. For such a setup, we demonstrate sub-millimeter accuracy of the two-way Time of Flight (ToF)-based localization, as well as high availability of the service (i.e., consistently more than 80% of the time), which is a result of the low energy consumed in localization. Finally, we provide the localization context for a number of relevant system parameters such as operational frequency, bandwidth, and harvesting rate.