Due to its critical impact on human health and the environment, monitoring and prediction of air pollution have become an important issue during the past decades. Non-linear behavior of air pollution in one hand and high volume of required data on the other hand, intensifies the complexity of air pollution prediction especially in online applications. In order to overcome the deficiencies of traditional methods, this study proposes an online algorithm based on Support Vector Machine (SVM) to predict the time series of air pollution in the city of Tehran, Iran. Prediction is performed on the basis of time series data of pollutant concentrations, weather condition, and geographical parameters such as traffic, surface curvature and local altitude. Evaluation of the outputs shows that prediction errors are within an acceptable range and the online algorithm has an outstanding speed in comparison with the conventional SVM. The overall accuracy of 0.71, RMSE of 0.54 and R² of 0.81 prove the efficiency of the proposed algorithm to develop a system to dynamically predict Tehran’s air pollution in advance.