This paper presents positioning algorithms for cellular network-based vehicle tracking in severe non-line-of-sight (NLOS) propagation scenarios. The aim of the algorithms is to enhance positional accuracy of network-based positioning systems when the GPS receiver does not perform well due to the complex propagation environment. A one-step position estimation method and another two-step method are proposed and developed. Constrained optimization is utilized to minimize the cost function which takes account of the NLOS error so that the NLOS effect is significantly reduced. Vehicle velocity and heading direction measurements are exploited in the algorithm development, which may be obtained using a speedometer and a heading sensor, respectively. The developed algorithms are practical so that they are suitable for implementation in practice for vehicle applications. It is observed through simulation that in severe NLOS propagation scenarios, the proposed positioning methods outperform the existing cellular network-based positioning algorithms significantly. Further, when the distance measurement error is modeled as the sum of an exponential bias variable and a Gaussian noise variable, the exact expressions of the CRLB are derived to benchmark the performance of the positioning algorithms.