This paper describes a novel, laser-based approach for tracking the pose of a high-speed mobile robot. The algorithm is outstanding in terms of accuracy and computational time, being 33 times faster than real time. The efficiency is achieved by a closed form solution for the matching of two lasers scans, the use of natural landmarks and fast linear filters. The implemented algorithm is evaluated with the high-speed robot Kurt3D (4 m/s), and compared to standard scan matching methods in indoor and outdoor environments.