In some embodiments, an apparatus and methods for storing data which self-compensate for erase performance degradation. Such an apparatus includes, in an exemplary embodiment, a plurality of memory blocks individually erasable during erase cycles by the application of erase pulses thereto having appropriate erase pulse voltage levels, and a memory location uniquely associated with each memory block that stores an initial erase pulse voltage level therefor to be used during an erase cycle. Such methods include, in an exemplary embodiment, counting the number of erase pulses applied to each memory block during an erase cycle therefor, comparing the count for each memory block to a threshold count value, and updating the stored initial erase pulse voltage level to be used during a subsequent erase cycle for each respective memory block if the count for that memory block is not less than the threshold count. Other embodiments are described and claimed.