Temperature effects in a non-volatile storage device are addressed by providing a data state-dependent, and optionally temperature dependent, sense current during verify and read operations. A different sense current is provided for each data state, so that a common temperature coefficient is realized for storage elements with different data states. The temperature coefficient for higher states can be reduced to that of lower states. During sensing, a sense time can be adjusted to achieve a desired sense current when a selected storage element is in a conductive state. A fixed voltage trip point may be maintained. During the sense time, a pre-charged capacitor discharges into a selected storage element such as via a bit line and NAND string, when the selected storage element is in a conductive state. The discharge level is translated to a current which is compared to a state-dependent, and optionally temperature dependent, reference current.