A dual-optimized adaptive Kalman filtering (DO-AKF) algorithm based on back propagation (BP) neural network and variance compensation was developed for high-sensitivity trace gas detection in laser spectroscopy. The BP neural network was used to optimize the Kalman filter (KF) parameters. Variance compensation was introduced to track the state of the system and to eliminate the variations in the parameters of dynamic systems. The proposed DO-AKF algorithm showed the best performance compared with the traditional multi-signal average, extended KF, unscented KF, KF optimized by BP neural network (BP-KF) and KF optimized by variance compensation (VC-KF). The optimized DO-AKF algorithm was applied to a QCL-based gas sensor system for an exhaled CO analysis. The experimental results revealed a sensitivity enhancement factor of 23. The proposed algorithm can be widely used in the fields of environmental pollutant monitoring, industrial process control, and breath gas diagnosis.