Particulate matter (PM) pollution in Southeast China has been worsening because of the rapid industrial development and urbanization, which have significant negative effects on atmospheric visibility. Characterization of the trend in atmospheric visibility is important for evaluating the impact of PM pollution on the impairment of visual air quality in urban and rural areas. Long-term trend in atmospheric visibility in Southeast China was analyzed for the period of 1973–2010 based on the meteorological data from the National Climatic Data Center (NCDC) database using four statistical methods: annual mean visibility, percentages of “very good” visibility and “bad” visibility, ridit analysis, and cumulative percentiles. The relationship of atmospheric extinction with Air Pollution Index (API) was studied. In addition, the effects of recent environment policies on visibility were studied. The results showed that the visibility had decreased in 94% stations of this region and prefecture stations had the highest decreasing trend of −3.1 km/decade during the entire period. The average visibility of all the 17 stations (i.e., region-average) declined at a rate of −2.0 km/decade, with a 38-year average of 18.1 km. Decrease in the percentage of “very good” visibility and increase in the percentage of “bad” visibility existed in 14 and 16 stations, respectively. Region-average percentage of “bad” visibility was in the range of 2.2–21.5%, with an increasing rate of 5.0% per decade, and that of “very good” visibility was 24.4–71.8%, with a decreasing rate of −10.7% per decade. During the entire period, county and prefecture stations had similar changing patterns and trends in visibility, while town stations had the least worsening trends. Region-average visibility was better before 1988 while worse after 1993 when comparing to the entire period, with the transition period of 1988–1993. The worst 20%, 50% and best 20% of region-average visibility declined at a rate of −1.6, −2.0 and −2.4 km/decade, with the average of 13.1, 17.8 and 23.0 km, respectively. During 2000–2010, the daily dry extinction coefficients were positively correlated with API with linear R2 values of 0.42 and 0.43 for Xiamen and Shantou, respectively, suggesting that the air pollution could be responsible for the visibility impairment in Southeast China. Analysis on the effects of recent policies suggested that visibility change was significantly positively correlated with environment treatment variables including Removed Industrial SO2 (RISO2), Total Investment in Environmental Pollution Control (TIEPC), Area of Green Space (AGS) and Removed Industrial Dust (RID), but significantly negatively correlated with Emission of Industrial Dust (EID). Time-lag effect on the contribution of TIEPC to visibility was found. It is suggested that continuous and effective pollution control strategy, particularly increasing investment in environment control and pollutant emission reduction, is needed to counteract the degradation of atmospheric visibility in Southeast China.