A method for programming in a non-volatile storage device, comprising: in a program operation, applying one or more initial program pulses (PPn-1, PPn) to one non-volatile storage element (230, 240, 250, 260, 270); during each program pulse of the one or more initial program pulses, setting a voltage (Vbl) of a bit line (BL0, BL1, BL2, BL3, BL4) associated with the one non-volatile storage element at an initial level (Vbl_0, V) which allows programming of the one non-volatile storage element; determining when a threshold voltage of the one non-volatile storage element exceeds a lower verify level (VvaL, VvbL, VvcL) of a target data state (A, B, C) of the one non-volatile storage element; when the threshold voltage of the one non-volatile storage element exceeds the lower verify level, applying additional program pulses (PPn+1, PPn+2, PPn+3, PPn+4) to the one non-volatile storage element, maintaining a count of a number of the additional program pulses which are applied to the one non-volatile storage element, and during the additional program pulses, stepping up the voltage of the bit line to different stepped up levels (Vbl_s1, Vbl_s2, Vbl_s3, Vbl_s3a) as a function of the count, the different stepped up levels are stepped up from the initial level and allow programming of the one non-volatile storage element; determining when the threshold voltage of the one non-volatile storage element exceeds a higher verify level (VvaH, VvbH, VvcH); and when the threshold voltage of the one non-volatile storage element exceeds the higher verify level, applying a next program pulse to the one non-volatile storage element, and during the next program pulse, setting the voltage of the bit line at a level which inhibits programming of the one non-volatile storage element. in a program operation, applying one or more initial program pulses (PPn-1, PPn) to one non-volatile storage element (230, 240, 250, 260, 270); during each program pulse of the one or more initial program pulses, setting a voltage (Vbl) of a bit line (BL0, BL1, BL2, BL3, BL4) associated with the one non-volatile storage element at an initial level (Vbl_0, V) which allows programming of the one non-volatile storage element; determining when a threshold voltage of the one non-volatile storage element exceeds a lower verify level (VvaL, VvbL, VvcL) of a target data state (A, B, C) of the one non-volatile storage element; when the threshold voltage of the one non-volatile storage element exceeds the lower verify level, applying additional program pulses (PPn+1, PPn+2, PPn+3, PPn+4) to the one non-volatile storage element, maintaining a count of a number of the additional program pulses which are applied to the one non-volatile storage element, and during the additional program pulses, stepping up the voltage of the bit line to different stepped up levels (Vbl_s1, Vbl_s2, Vbl_s3, Vbl_s3a) as a function of the count, the different stepped up levels are stepped up from the initial level and allow programming of the one non-volatile storage element; determining when the threshold voltage of the one non-volatile storage element exceeds a higher verify level (VvaH, VvbH, VvcH); and when the threshold voltage of the one non-volatile storage element exceeds the higher verify level, applying a next program pulse to the one non-volatile storage element, and during the next program pulse, setting the voltage of the bit line at a level which inhibits programming of the one non-volatile storage element.