Air pollution is a major problem in the world today, causing undesirable effects on both the environment and human health and, at the same time, stressing the need for effective simulation and forecasting models of atmospheric quality. Targeting this adverse situation, our current work focuses on investigating the potential of data mining algorithms in air pollution modeling and short-term forecasting problems. In this direction, various data mining methods are adopted for the qualitative forecasting of concentration levels of air pollutants or the quantitative prediction of their values (through the development of different classification and regression models respectively) in five locations of the greater Athens area. An additional aim of this work is the systematic assessment of the quality of experimental results, in order to discover the best performing algorithm (or set of algorithms) that can be proved to be significantly different from its rivals. Obtained experimental results are deemed satisfactory in terms of the aforementioned goals of the investigation, as high percentages of correct classifications are achieved in the set of monitoring stations and clear conclusions are drawn, as far as the determination of significantly best performing algorithms is concerned, for the development of air quality (AQ) prediction models.