Programming speed for multi-level non-volatile storage elements is increased by reducing the number of verify operations. In one approach, verify operations are initially performed for the highest state less frequently than for other, lower states based on a recognition that a wider threshold voltage distribution for the highest state can be tolerated. After a number of additional programming pulses are applied, the frequency with which the verify operations are performed for the highest state increases. For example, for a four-level device in which state C is the highest state, C-state verify operations can be started when a first B-state element has been programmed and an additional number of program pulses have been applied. The C-state verify operations can be performed after every other program pulse until a certain number of C-state elements have been fully programmed, after which the C-state verify operations can be performed after every program pulse.