Feature extraction by time-series analysis and decision making through distance-based methods are powerful and efficient statistical pattern recognition techniques for data-driven structural health monitoring. The motivation of this article is to propose an innovative residual-based feature extraction approach based on AutoRegressive modeling and a novel statistical distance method named as Partition-based Kullback–Leibler Divergence for damage detection and localization by using randomly high-dimensional damage-sensitive features under environmental and operational variability. The key novel element of the proposed feature extraction approach is to establish a two-stage offline and online learning algorithms for extracting the residuals of AutoRegressive model as the main damage-sensitive features. This technique brings the great benefit of reducing the computational time and storage space for feature extraction in long-term monitoring conditions. The major contribution of Partition-based Kullback–Leibler Divergence method is to exploit a partitioning strategy for dividing random features into individual partitions and utilize numerical information of partitioning in distance calculation rather than directly applying random samples. Dealing with the major challenging issue of using the high-dimensional features in decision making and applicability to both correlated and uncorrelated random datasets are the main advantages of Partition-based Kullback–Leibler Divergence method. The accuracy and reliability of the proposed approaches are experimentally validated by two well-known benchmark structures. The stationarity and linearity of measured vibration responses for using in AutoRegressive modeling are evaluated by two hypothesis tests. Comparative studies are also conducted to demonstrate the superiority of the proposed methods over some exciting state-of-the-art techniques. Results show that the methods presented here succeed in detecting and locating damage and make time-saving and efficient tools for feature extraction and damage diagnosis.