A system is disclosed for programming non-volatile storage that improves performance by setting the starting programming voltage to a first level for fresh parts and adjusting the starting programming voltage as the memory is cycled. For example, the system programs a set of non-volatile storage elements during a first period using an increasing program signal with a first initial value and subsequently programs the set of non-volatile storage elements during a second period using an increasing program signal with a second initial value, where the second period is subsequent to the first period and the second initial value is different than the first initial value.