The paper presents a new endoscope motion tracking method that is based on a novel external endoscope tracking device and our modified stochastic optimization method for boosting endoscopy navigation. We designed a novel tracking prototype where a 2-D motion sensor was introduced to directly measure the insertion-retreat linear motion and also the rotation of the endoscope. With our developed stochastic optimization method, which embeds traceable particle swarm optimization in the Condensation algorithm, a full six degrees-of-freedom endoscope pose (position and orientation) can be recovered from 2-D motion sensor measurements. Experiments were performed on a dynamic bronchial phantom with maximal simulated respiratory motion around 24.0 mm. The experimental results demonstrate that our proposed method provides a promising endoscope motion tracking approach with more effective and robust performance than several current available tracking techniques. The average tracking accuracy of the position improved from 6.5 to 3.3 mm, which further approaches the clinical requirement of 2.0 mm in practice.