In previous studies, two traffic data-cleaning algorithms were developed at the Institut National de Recherche sur les Transports on the basis of filtering techniques and statistical approaches. Because of their mathematical structure (linearity of the process), both algorithms present a high level of inaccuracy in the case of nonhomogeneous traffic conditions at the location of the measurement stations (for example, free flow upstream and congestion downstream, or vice versa). A new algorithm for solving the traffic data-cleaning problem on the basis of real-time application of a dynamic first-order modeling approach was devised to take into account the nonlinearity of the traffic phenomenon. The developed algorithm, named PROPAGE, was tested using real data measurements, including a wide spectrum of traffic conditions. Compared with results from previous algorithms, the results obtained were more accurate.