An optimal control law was suggested for on-line tracking in the terrain following. To circumvent difficulties arising from the nonlinearity of the flight dynamics and the boundedness of realistic control inputs, the optimal decision strategy (ODS), which is a pointwise optimization technique, was employed. The flight vehicle dynamics was cast into the linear form with respect to the control inputs to apply the ODS technique to the present terrain following problem. The terrain following problem when formulated in terms of Mach number and flight path angle belongs to the case that the number of the state variables is larger than that of the control variables. A general form of the desired velocity command for this case was derived. With the desired velocity command, the optimal control law was obtained in a closed form and the stability of the system was examined. The desired trajectory necessary to implement the optimal control law was planned based on constant energy assumption. The control strategy based on the Mach number and flight path angle formulation has a drawback in the sense that the height tracking error can be hardly reduced when subjected to ill posed path or numerical errors. This situation can be remedied by restating the vehicle dynamics in terms of Cartesian velocity components. An optimal control law and the desired velocity command for the transformed system were given. The proposed optimal control law guaranteed that height tracking error was always reduced. To demonstrate the feasibility and effectiveness of the proposed on-line optimal tracking algorithm, numerical simulations were carried out. The results of the simulation confirmed that the suggested on-line optimal tracking algorithm was a good alternative for the terrain following.