Prospective studies concerning sleep architecture and cognitive function have focused on individual sleep measures per se, without considering the complementary role of non-REM (NREM) and REM sleep. We explored the association between NREM/REM cycle-related sleep architecture and cognitive decline. Community-dwelling elderly people in Korea from the Korean Longitudinal Study on Cognitive Aging and Dementia were enrolled. They were cognitively normal and underwent overnight polysomnography at baseline. A NREM/REM cycle is a sequence of NREM and REM sleep, uninterrupted by a waking period of >2 min. After 4 years, the development of mild cognitive impairment (MCI) or dementia was related to the measures of sleep architecture, including NREM/REM cycle parameters by logistic regression analyses. Of 235 participants (mean [SD] age 68 [5] years; 60% female) at baseline, 14 (5.9%) developed MCI/dementia at follow-up. A short average cycle length (OR, 0.97 [95% CI, 0.94–0.99]; p = 0.02) was significantly associated with cognitive decline. When its substructure and NREM and REM sleep outside of cycles were considered simultaneously, the average REM sleep duration per cycle (OR, 0.87 [95% CI, 0.76–0.98]; p = 0.03) was significantly related to the outcome. In conclusion, short average duration of NREM/REM cycles, especially average REM sleep duration in each cycle, in cognitively normal elderly might be used as an early marker of cognitive decline.