Based on dust storm frequency (DSF) data from the China Meteorological Administration, Arctic sea-ice concentration (SIC) data from the Hadley Centre, and atmospheric reanalysis data from the National Centers for Environmental Prediction (NCEP) and National Center for Atmospheric Research (NCAR), temporal variations and regime shifts of East Asian DSF and Arctic SIC during 1961–2015 are revealed, and the possible relationship between them is explored. The results show that East Asian DSF in spring is closely associated with the preceding winter SIC from the northern Greenland Sea to the Barents Sea (20° W–60° E, 74.5° N–78.5° N). In the past half-century, both East Asian DSF and Arctic SIC have shown significant declining trends, with consistent regime shifts in the early 1980s. Further statistical analyses indicate that the abrupt decrease of East Asian DSF in spring may be attributed to the concurrent sharp loss of Arctic SIC in the preceding winter. It is the loss of Arctic SIC that causes the atmospheric circulation anomalies downstream by stimulating a Rossby wave train, resulting in decelerated wind speed, dampened vertical wind shear and restrained synoptic-scale disturbances over the dust source region, eventually leading to the decline in East Asian DSF over decadal timescales.