The two-headed kinesin motor harnesses the energy of ATP hydrolysis to take 8-nm steps, walking processively along a microtubule, alternately stepping with each of its catalytic heads in a hand-over-hand fashion. Two persistent challenges for models of kinesin motility are to explain how the two heads are coordinated ("gated") and when the translocation step occurs relative to other events in the mechanochemical reaction cycle. To investigate these questions, we used a precision optical trap to measure the single-molecule kinetics of kinesin in the presence of substrate analogs beryllium fluoride or adenylyl-imidodiphosphate. We found that normal stepping patterns were interspersed with long pauses induced by analog binding, and that these pauses were interrupted by short-lived backsteps. After a pause, processive stepping could only resume once the kinesin molecule took an obligatory, terminal backstep, exchanging the positions of its front and rear heads, presumably to allow release of the bound analog from the new front head. Preferential release from the front head implies that the kinetics of the two heads are differentially affected when both are bound to the microtubule, presumably by internal strain that is responsible for the gating. Furthermore, we found that ATP binding was required to reinitiate processive stepping after the terminal backstep. Together, our results support stepping models in which ATP binding triggers the mechanical step and the front head is gated by strain.