The Chinese government has put forward a series of aggressive control measures to tackle environmental problems, such as poor visibility, since the first year of its 11th five-year plan (2006-2010). Recently recorded visibility, air quality and meteorological data in four major megacities (Beijing, Shanghai, Guangzhou and Chengdu) in different haze regions (and climatic zones) of China were analyzed with the aim of evaluating the extent to which the control actions have affected these measures. The ambient concentrations of three major air pollutants (SO2, NO2 and PM10) in these cities all decreased in the years 2005-2009. However, improved visibility was observed only in Beijing and Guangzhou; it remained steady in Shanghai, and showed a decreasing trend in Chengdu. The results highlight the fact that the correlation between air quality and visibility is complex. Optimal empirical regression models were developed, based on measured air quality and meteorological parameter data, to better isolate possible causal correlations between visibility and air quality, as well as meteorological conditions. Our results show that the improvement in visibility in both Beijing and Guangzhou was mainly due to the reduced PM10 concentration. In Guangzhou, improved atmospheric visibility was also helped by a reduction in SO2 concentration in winter. In contrast, lower wind speed, together with possible changes in fine particle concentration and composition, could explain why no improvement in visibility trend was found in Shanghai or Chengdu.