Abstract This paper proposed a data-driven speech enhancement method based on the modeled long-range temporal dynamics (LRTDs). First, by extracting the Mel-Frequency Cepstral coefficient (MFCC) features from speech and noise corpora, the Gaussian Mixture Models (GMMs) of the speech and noise were trained respectively based on the expectation-maximization (EM) algorithm. Then, the LRTDs were obtained from the GMM models. Next, based on the LRTDs, a modified maximum a posterior (MAP) based adaptive longest matching segment searching (ALMSS) method derived from A* search technique was combined with the Vector Taylor Series (VTS) approximation algorithm in order to search the longest matching speech and noise segments (LMSNS) from speech and noise corpora. Finally, using the obtained LMSNS, the estimation of speech spectrum was achieved. Furthermore, a modified Wiener filter was constructed to further eliminate residual noise. The objective and subjective test results show that the proposed method outperforms the reference methods.