Techniques and circuitry are disclosed for implementing non-volatile storage that exploit bias temperature instability (BTI) effects of high-k/metal-gate n-type or p-type metal oxide semiconductor (NMOS or PMOS) transistors. A programmed bitcell of, for example, a memory or programmable logic circuit exhibits a threshold voltage shift resulting from an applied programming bias used to program bitcells. In some cases, applying a first programming bias causes the device to have a first state, and applying a second programming bias causes the device to have a second state that is different than the first state. Programmed bitcells can be erased by applying an opposite polarity stress, and re-programmed through multiple cycles. The bitcell configuration can be used in conjunction with column/row select circuitry and/or readout circuitry, in accordance with some embodiments.