The rapid industrial development and urbanization has led to increasing particulate matter pollution in the Cross Taiwan Strait Region, which has significant impacts on atmospheric visibility degradation. Long-term visibility trends in five typical cities over the cross-strait region (i.e., Xiamen and Fuzhou in the Western Taiwan Strait (WTS) region and Taipei, Taichung and Tainan in Taiwan) and its correlation with air quality and meteorological conditions were investigated using visibility and meteorological data during 1973–2011 and air pollution data during 2009–2011. For the entire period, the overall average visibilities in the WTS region were better than those in Taiwan, with an average of 16.8, 16.6, 8.5, 10.3 and 9.0 km in Fuzhou, Xiamen, Taipei, Taichung and Tainan, respectively. Decline trends with decreasing rates of  -0.5–0.1 km/yr existed in all cities except Taipei, which had an improvement in visibility after 1992. All seasons had decreasing trends during the 39-year period except in Taipei. The WTS region had the worse change trend compared with Taiwan. No statistically significant weekend effect in visibility is found over the region. Visibilities were better in summer and autumn, while worse in winter and spring. Correlation analysis revealed that significant negative correlations existed between visibility and NO₂ and airborne particles (i.e., PM10 and PM2.5); PM2.5 played an important role in visibility degradation. High temperature and low pressure is beneficial for better visibility. Principal component analysis further confirmed the impacts of high concentrations of air pollutants, stable synoptic systems and humid air with high relative humidity on visibility impairment. In addition, case studies highlighted characteristics and potential causes of typical regional low visibility episodes over the region.